| |
Genetic Algorithm
(View Java Source Code for Driver)
(View Java Source Code for Population)
(View Java Source Code for Linux Console Driver)
I am very new to the field of evolutionary
programming. Ever since I attended a lecture on the structuring of GA's
(or, "genetic algorithms"), I had wanted to take up the challenge of
creating a simple, if not crudely designed genetic or evolutionary
algorithm. I had begun by trying to develop one using Perl, but the
verbosity and complexity of the language seemed to require work that
overshadowed the development of the algorithm itself. I switched over
to Java, which had a few problems of its own.
Here is a customizable setup to view my GA. You may
need a quick processor and recent browser to view it correctly, and you
must have Java enabled on your machine. Scroll down if you want to
learn more about this program!
Here is how my algoritm is working:
| 1. |
The program creates a group of n individuals, each with
a random build-up of x genetic traits. (Thus, the program uses
a double vector array: "people[n][x]".) Each trait is valued between
0 and 3 (inclusive), and selected from a random number generator with a
fixed seed. This ensures that every time you run the program, you will
begin with the same sampling of genes. |
| 2. |
[Generation begins.] A random "person" is selected by a
non-seed-based random number generator, and a "mate" is similarly
selected. There is an equal likelihood of each "person" being paired up
with another, and at this point each person's strength does not
matter. |
| 3. |
Copies of the current "parents" are made. Consider these
copies to be "children." |
| 4. |
A total of half of randomly selected traits of the "children"
are swapped. (Again, the selection of the traits is based on a
non-seed random number.) |
| 5. |
Each of the children are passed to a method which mutates random
traits. The number of traits (or "mutation factor") depends on the
value chosen by the user; the higher the percentage, the more traits
will be mutated. (Note that this step may be skipped if the user
chooses not to allow mutations to occur.) |
| 6. |
Once the two parents and two children (four total) are made,
one of two things can happen, according to the user's pre-execution
preference.
- Non-Darwinian method: Here, the children
replace the parents and take their place in the original group.
Strength of the parents and children do not matter.
- Darwinian method: Of the four people, the two
strongest are selected and placed into the parent's position in the
main group. Any pair of the total of four can be placed back into
the group, provided that the said pair is the strongest of the
current family.
|
| 7. |
The positions of the original parents are marked-off as not
selectable. They will be selectable when all n individuals
(or n-1 individuals if the population is odd) have found a pair.
This ensures "monogamy," such that no one person can pair-up with more
than one other person in a single run. |
| 8. |
Repeat from step 2, until the entire population has had a
chance to pair-up and create offspring. |
| 9. |
Repeating steps 2 through 8 generates an open-ended run. |
There are more unimportant details to be noticed during execution.
Namely, instead of seeing a bunch of 0's, 1's, 2's and 3's, the numbers
have been converted to A's, G's, T's, and C's respectively. Also, the
strength of each gene splice is written on the right hand side of the
gene.
| |
