The Search API PackageThis package contains the specification and base classes of the Common Search API of the DGPF.
All search algorithms provided come with an auto-adaptive, configurable Tabu Search backend. If a client/server distribution is chosen, the backend executes on the server, reducing network traffic.
algorithms.ga provides the basic ability of genetically evolving solutions
for any type of problems. Multi-objective Genetic Algorithms
are be implemented using different distribution schemes in the package
which bases on the versatile search api provided by the Search-package.
The idea behind genetic evolving problem solutions is the following: You have an idea on some qualities a thing should have, but you donít know what this thing is or how it should be created. The genetic approach might answer this question. At first, a set of random things is created. From this set we take those things that match your idea the best (using the fitness function). These we modify slightly or combine with each other to find a new set of things. This we do again and again, until we have found the ideal thing or we are close enough to what we want. For more information, visit the Genetic Programming Group at http://groups.google.de/group/geneticprogramming/ or for example http://www.genetic-programming.org/.
Genetic algorithms can be performed on a single computer. Therefore, the LocalGeneticEngine is intended.
Genetic algorithms have a high parallelizing potential. There are many common methods for parallelizing them known. In "Island Hopping" for example, many populations of solution-candidates, so called individuals, can be evolved on different machines. By exchanging their best individuals, the populations are loosly coupled. This mechanism is implemented in one genetic engine called P2PGeneticEngine, where P2P means peer-to-peer, because it basically realizes a peer-to-peer network.
We support four different types of distribution of computational load for our genetic algorithms:
algorithms.ga comes with very simple interfaces that allow you to unleash
the potential of genetic algorithms without needing to think about network
stuff. Any sort of thing/problem can be evolved, you just need to make sure
that your individuals are serializable and then specify a fitness function
and provide reproduction facilities.
The GA package allows you also to customize the parameters of the evolution in a simple manner: you can the mutation/crossover rate, the selection algorithm, the population size or the emigrant- and immigrant-ratio and such and such on every generation, basing your decisions on extensive statistical data gathered. Therefore you also can implement a class that performs those decisions automatically - or you can use the default values. You may restrict the generation count or the evolution time as well as specify a ideal-threshold fitness value (the evolution stops when one individual with such a fitness or even a better one occurs).
The GA provides full support for multi-objective Genetic Algorithms. To be precise, one can specify an arbitrary count of fitness functions to be evaluated for each individual. This allows you to evolve individuals which have more than one desired property optimized. Therefore, the evaluation function of the genetic environment is simulation based. Each fitness function may create a data record for individuals being evaluated. This record serves as repository for information on the individual when it is simulated. A simulation consists of a specified count of steps. Each fitness function might specify a count of steps after which it will inspect the state of the simulation and update its records.
At the end of a simulation, each fitness functions evaluates its records and determines one fitness value. To obtain stable results, each individual will be simulated more than once. After all simulations of an individual are done, statistic records on the single fitness values assigned are provided to the fitness functions, so that they can compute the final fitness value. By default, this will be the median of the different test results (or the average if only a few simulations have been performed).
The statistic evaluation is rich: for each distinct fitness function there exist statistic records for the final fitness values of the populationís individuals. After receiving all single final fitness values, the client calculates one overall fitness values per individual. This value then goes through different filters, allowing the evolution to be controlled or steered in a specific direction. Various distribution methods for Genetic Algorithms are available, like "island hopping" which would now perform emigration and immigration.
Whatsoever, the GA package can still be used for such simple things like finding the root of some arithmetic functions which is presented as example amongst others in the Examples package also available online.
Like Genetic Algorithms, Hill Climbing is implemented in four distribution flavours: locally running, client/server, p2p and p2p-client/server hybrid distributed.
Like Genetic Algorithms, Simulated Annealing is implemented in four distribution flavours: locally running, client/server, p2p and p2p-client/server hybrid distributed.
Search algorithms are executed by
SearchEngines. The names of the
search engines are formed like this: The distribution shortcut + the algorithm
This Open-Source research project is licensed under LGPL, a license even more liberate than the GPL.
See the rich example collection also available on the web for feature demonstrations.
One feature, especially important for developers, is the full documentation of the source code provided. Each method, class, package is fully documented down to privated declares. No parameter is undocumented. We are also happy about hints or request for more documentation, because we want that anyone can use our code and hopefully understand it. This project has also educational character.
You can find more information on the project's home page or on the project's page on SourceForge. The source code and examples can be downloaded at the downloads page. Useful information and news will frequently be published in the Genetic Programming Group.