OpenSolaris

Development of a Library of Genetic Algorithms for the Applications involving Dynamic Data Sets

Joseph Jeffery - lead student researcher  Alex Aravind - faculty advisor  Steven Mclean - student researcher

University of Northern British Columbia, Prince George, BC, Canada

Final Report [PDF]

Try the Genetic Algorithm User Interface

Purpose

To develop a library of genetic algorithms on the OpenSolaris operating system platform that can be used to solve optimization and estimation problems involving dynamic data sets. Although genetic algorithms are very attractive for many practical applications involving optimization and estimation, they have not traditionally been used in practice due to their high computational requirement. Recent multi threading technology and exponential speed increases have begun to remove this hurdle by offering high level of computing power, an area in which and Sun is considered a world leader.

Background

Although the basic ideas of genetic algorithms were introduced as early as 1960's and applicable for variety of applications [1,3,4], they are generally popular only within the Artificial Intelligence Community. Recently, research has gone through a revival in the field of evolutionary computation, enough at least for the Association of Computing Machinery to charter a special interest group on the topic (ACM SIGEVO). Genetic algorithms, a subset of evolutionary computation, gain their robustness and efficiency by working essentially in the same way as natural processes. By modeling the Darwinian process of survival of the fittest and random mutation, GA's can act as a heuristic to quickly converge to an efficient solution to NP-hard problems. This is perhaps not the globally optimal solution, but the results given may be "good enough" given the problem at hand. For example, layout on VLSI circuits can be quickly optimized to a state where the cost of manufacture versus the cost of engineering a more efficient layout falls on the side of using the less optimal computationally derived solution. Another example is in the field of web traffic analysis [5]

As much as we currently know about the utility of genetic algorithms is dwarfed only by what we may not know about them. Evolutionary computation is still a field wherein there are many unexamined facets remaining. One such mostly unexplored facet in the field is the role evolutionary algorithms can play when applied to dynamic data sets, data which may not have the optimal solution from one iteration of an algorithm to the next, rather than the pre-set static data set that genetic algorithms have traditionally been applied to. That is, using genetic algorithms to find a best general strategy for converging on the average of a constantly in flux definition of "fitness". Traditionally, genetic algorithms have not been exploited in analyzing and adapting to dynamic data do in large part to the massive computational & parallelization requirements to do so. A solution to this problem may have applications in computerized stock trading, manufacturing, etc. The other subfield applicable to this research is the role that antagonistic evolutionary algorithms can play in optimizing the solution. In nature, we are not confronted with a static set of isolated life forms reproducing or dying based solely on arbitrarily imposed measures of fitness. Rather, we find in any ecology both the environment and the other life forms influencing the standard of fitness. That is to say, the terrain and other natural features change in the long term, but in the shorter term the abundance of predator or prey in the domain enable a much faster evolutionary reaction. It is for this reason we believe that to effectively deal with dynamic data sets, the quick reaction time afforded by this sort of antagonistic co-evolution may prove to be an invaluable tool.

Approach

We intend to organize the software library into two components: front end - a graphical user interface (GUI) for the users to convenient feed the input and use the software and a back end – the core library of genetic algorithms. The back end will be developed first and then the GUI will be designed and implemented to integrate with the front end. In these, development of back end involves major effort. Genetic algorithms typically have two major components: the function which determines fitness, and the genetic schemas. Schemas are typically generated randomly initially, and the function of fitness is determined by the environment and desired result. A usual fitness function proceeds to a greater or lesser degree as follows: First the schemas are generated randomly, then they are all evaluated by the fitness function. Those that are determined to be more fit than the average are duplicated, with some chance of random mutation, and some chance of being “crossed over” or “bred” with other schemas in the next round. Those that are determined to be less fit are deleted. The fitness evaluation function is then evaluated on the new schemas, etc until the desired result is reached. We intend on allowing this fitness function to be changed between iterations of the evaluate-replicate-mutate cycle. We also intend on allowing the fitness function to take the preponderance of sub-schemas as one parameter in the fitness calculation.

We will carry out these developments in multiple phases.

Phase 1: Implementation of a library for modeling genetic algorithms for static data. This involves implementing the data structures for gene modeling which will take a static function as a measure of fitness to apply the Darwinian “survival of the fittest” notion by, the algorithms for crossover and mutation by iteration, and careful attention to ensuring that critical sections are minimized and the algorithms are thread safe. Additionally, we will place DTrace probes throughout the library to help diagnose problems and inefficiencies.

Phase 2: The algorithms will be tuned to work with dynamic data sets. This tuning initially involves modifying the previous library such that it the fitness function can be changed at any time programattically. The algorithm will also be extended to allow the preponderance of schemas of a certain class to be observable to the fitness subalgorithm, such that it can be passed as a parameter to fitness. Using the previously mentioned DTrace probes, these extensions will be analyzed and optimized.

Phase 3: Design and implementation of GUI.

Phase 4: Integration of front end and back end.

Phase 5: Data collection and analysis. After which a paper will be compiled for possible publication

Technology Goals

We intend to create a C library on the OpenSolaris platform whose purpose is to evaluate genetic schemas heuristically based on a dynamic measure of fitness which can accept the preponderance of other schemas as a parameter. We will take advantage of the OpenSolaris operating system in many ways, including exploiting the operating system’s best-in-class threading capabilities, thread synchronization support, and integrating DTrace as a key tool for tuning the algorithm

Expected outcome

We expect to see an antagonistic model provide a significant speed up in the ability for a genetic algorithm to adjust to change in the fitness calculation function, allowing the system as a whole to adapt to incoming dynamic data much more effectively than traditional models.

References

1. Branke, Jürgen. Evolutionary Optimization in Dynamic Environments. Norwell, Massachusetts: Kluwer Academic Publishers, 2002.
2. Xiufen Zou, Wang, M., Anmin Zhou, Mckay, B. "Evolutionary optimization based on chaotic sequence in dynamic environments." Proceeding of the IEEE International Conference on Networking, Sensing and Control, 1364-1369, 2004.
3. Michalewicz, Zbigniew. Genetic Algorithms + Data Structures = Evolution Programs. Berlin Heidelberg: Springer-Verlag, 1996.
4. Mitchell, Melanie. An Introduction to Genetic Algorithms. Boston, Massachusetts: Massachusetts Institute of Technology, 1996
5. Bonino, D., Corno, F., Squillero, G. “A Real-Time Evolutionary Algorithm for Web Prediction.” Proceedings of the IEEE International Conference on Web Intelligence, 139-145, 2003.
6. Arenas, M.G. and Collet, P. and Eiben, A.E. and Jelasity, M. and Merelo, J.J. and Paechter, B. and Preuß, M. and Schoenauer, M. A framework for distributed evolutionary algorithms