I am interested in evolutionary computing and genetic algorithms (GA).
In 1995, I wrote PathGen, a little Windows program that demonstrates the power of the GA techniques in solving a computationally hard problem. PathGen is aimed to find approximate solutions to the Traveling Salesman problem, that is, to find the shortest path connecting a given set of points. This is a problem with no solution known, apart from the exhaustive search among all possible paths, which quckly leads to combinatory explosion of computation time as the number of points increases.
PathGen screenshots while evolving a solution for 80 random points
Download PathGen (ZIP, 583 KB)
No setup is required, just unzip all files in the same directory and run PathGen.exe. The program usage is very easy: with the mouse, draw the points on the window and then press the rocket button to start the GA. Usually, good solutions come out in a few seconds. The exhaustive search algorithm is also implemented for speed comparison (bicycle button).
In conjunction with developing the program, I explained the problem and my approach to it in the following magazine article (in Italian), also included in the above zip file:
F. Fusco, Una variante dell'approccio genetico applicata al problema del commesso viaggiatore (PDF, 143 KB), Minds & Bits - Bollettino del SIG Computer Italia, n. 5 (Aprile 1996).
The point made in the article is that for optimization problems that leads to DNA reshuffling (as this approach to the Traveling Salesman problem), the classical GA breeding operations are not suited, since there is no continuity between genotype and phenotype. This forces to abandon sexual reproduction in favour of asexual reproduction. Adopting this choice, the DNA variety of the gene pool can be obtained only by mutation, which rate shall be therefore quite high (around 90%). With such a mutation rate, the selective pressure shall be strong, otherwise promising solutions can readily get lost. Pushed to its limit, this implies that the fertile individuals could be reduced at just the best in the population: the "queen bee".
Although GA are best suited for global optimisation, to some extent they can be applied to robot planning and control. In this case, every generation of the algorithm is seen as a meaningful step of a control loop, not only as an intermediate result. Obviously, with this approach the problem of local minima is a major concern.
In this interactive demo, you have a 19-DOF manipulator with one extreme fixed to a basepoint and the other one free. It moves in two dimensions for simplicity, but can be easily extended to 3D. The mission consists in reaching a target (cross symbol) while avoiding and a few obstacles at the same time (red symbols). Both target and obstacles are draggable with the mouse.
After opening the interactive demo, assign the desired goal by selecting one of the options on top and see what happens. The robot behavior can be improved by changing goal along the execution. For instance, in certain situations the robot may be trapped between obstacles, then one may try to temporarily change the goal to "Retract" or to something else, then to go back to "Follow target". Techniques for doing this automatically may be studied.
As this is a work in progress, any comment and suggestion is welcome.
Third-party libraries used:
(1) Graphics from "WZ Jsgraphics" (C) by Walter Zorn
(2) Drag-drop from "Collision Detection" (C) by Kurt Grigg
(3) Power level indicator from "Percent Bar" (C) by Brian Gosselin
Another interesting field for GA is portfolio optimization. The problem can be stated in many ways. The most typical is the following: given a certain risk aversion, find the portfolio allocation that maximizes the expected global return, maintaining the global standard deviation below the given risk aversion.
The forecast is based on the historical data of a given set of assets (stocks, bonds, bills, funds, currencies, or whatever). Of course the underlying assuption in this kind of things is that data from the past are somehow representative of future risks and returns, which is an arguable point.
My Portfolio Optimizer (XLS, 164 KB) is an Excel spreadsheet based on the classic GA approach and implemented as macro.
Data contained in the spreadsheet are representative of a set of Italian funds over a quite short period. They can be changed to other scenarios, with some manipulation.
Start from the first spreadsheet page ("Data") and replace the table with your actual data. The sampling data period is one month (which is considered too short by many financial analysts: you can change it, in that case some obvious formula modification is required).
Move to the second page ("Analysis") and check that all table ranges are consistent with the input data at the previous page (use copy and paste to add rows and columns, to inherit formulas). The Analysis page also gives a visual impression of asset returns for each sampled period, and of asset correlations over all periods (the lower is the correlation between two assets, the better is to have them together in a portfolio).
Finally, move to the third page ("Optimizer") and you are ready to go. On top, you have the single asset class performances, that is, the separate performances of each asset, calculated from the previous pages. Then the asset weights: this is the output of the problem. After running, that row will contain your portfolio allocation. The Start button activates the GA. As the algorithm has no termination condition, it will run as long as you don't press Stop.