On October 9, 1997 I successfully defended my thesis and completed my master’s degree in Mathematical Sciences. The topic of my research involved Genetic Algorithms and their application in curve-fitting and function optimization.
Genetic Algorithms are computational models which simulate the behavior of natural systems, like biological reproductive systems. Their structure is likened to Darwin’s theory of Evolution, where ‘survival of the fittest’ in candidate solution strings takes over and the best fit candidates dominate the population. Through iteration this eventually leads to the optimal solution (at least this is the hope).
The topic of my research dealt with applying GAs to two very distinct problems:
- function optimization with fitness dependent on an objective function value and an auxilliary condition (stability).
- Curve-Fitting – The first application involved fitting satellite altimeter data provided by the Navy’s GEOSAT satellite of the Gulf stream region to the following equation proposed by Matthew Lybanon of the Naval Remote Sensing Branch:
SSH = A tanh[B(X – D – E)] – F tanh[C(X – E)] + G
Altimeter data collected by the satellite tends to be contaminated with the mean Gulf Stream topography. Using the above equation to estimate the contamination and then remove it has been shown to be a successful approach.
I have modified existing GA software to find these coefficients A -> G based on the satellite data in surprisingly little computation time. The results obtained with my GA are comparable to results obtained by the Naval Remote Sensing Branch.
- Optimization – The second application involved finding the optimal solution for the Stable Marriage problem of order n. A stable marriage is a one to one pairing of a set of men to a set of women so that no man and woman would agree to leave their assigned partners in order to marry someone else. This problem actually has quite a few very practical applications such as matching internships with candidates, doctors with their assigned residencies, etc. You might be surprised at how often this type of problem is used in the real world.
Although my GA does find the optimal solution consistently, the estimated convergence time is not satisfactory. Possible solutions to this were illustrated and the research provided a good starting point for anyone looking to optimize the procedure to be a suitable method for solving the problem for any population size.
Genetic Algorithms work suitably well at solving both of these problems in competitive computation times. If GAs sound interesting to you be sure to check out the comp.ai.genetic newsgroup.