Homework #1

Tal Bereznitskey(060403144) & Yoav Vardi(060414562)

Question #1

All possible schemata:

01011	*1011	0*011	**011	01*11	*1*11	0**11	***11
010*1	*10*1	0*0*1	**0*1	01**1	*1**1	0***1	****1
0101*	*101*	0*01*	**01*	01*1*	*1*1*	0**1*	***1*
010**	*10**	0*0**	**0**	01***	*1***	0****	*****

Dropping the assumpation would prevent us from calculating the average, since there is no way of telling which genotypes are present.

Question #2

Schemata	Tot.	Avg.
1***1	4976	622
0****	1376	86
11111	993	993
*****	10944	342
00**0	72	18
11*1*	3384	846

Question #3

• a.
  • for (*****111) the order is 3 and the defining length is 2
  • for (1*****1*) the order is 2 and the defining length is 6
• b.
  • probablity of surviving a mutation for (*****111) is (0.999)³ = 0.997
  • probablity of surviving a mutation for (1*****1*) is (0.999)² = 0.998
• c.
  • probablity of surviving a crossover for (*****111) >= 1-((0.85)*2/(8-1)) = 0.757
  • probablity of surviving a crossover for (1*****1*) >= 1-((0.85)*6/(8-1)) = 0.271

Question #4

Source code:

• q4.java (main)
• genotype.java
• pop.java
• Fitness.java

Problem description: Finding the Min(g(x,y))

Process of work: We started by defining and implementing a genotype representation (as described below), then we built a fitness-proportionate-selection based GA where fitness function, crossover and mutation rates were as stated in the question.

Genome representation: We considered a couple of representations:

1. First, we divided the range to X intervals, each gene had X bits. The number of 1's in the gene tells us how many intervals to "jump" starting from the lower bound of (-2).
   ie. if X=10 then a gene 1001000010 will be translated to a phenotype of: 3 * (4/10) + (-2) = -0.8
   A full genotype included two genes, one for the X and for the Y variable.
2. The previous representation worked fine, but was extremely memory consuming (X bits gave us X options). Therefore we turned to binary representation where X bits gave us 2^X options and therefore an increased precision for the same memory cost.

Results: The algorithm usually finds the minimum of function g(x,y) (as seen in plots 1-4), although in some cases, a local minimum is found instead (plot 5).

Conclusions: The minimum problem can be solved using a GA, a higher mutataion rate might solve the local minimum probleam.

Plots:

Question #5

Getting "stuck" does not mean an optimal solution has been reached.
possible solutions for getting "stuck": raising the mutation rate, intreducing new genomes into the population.

Question #6

Source code:

• q6.java (main)
• genotype.java
• pop.java
• Fitness.java
• Primes.java

Problem description: Finding the minimum prime numbers smaller than 100, who sums up exactly to 473.

Process of work: After we found the list of primes, we implemented an GA similar to the one in q4.
We chose a fitness function which rewards smaller distances from our target (437). this method worked well, so we added the minimum group size constraint to the fitness function.
For the bonus question, we experimented with some of the factors, leading to non-optimal results (18).
Analyzing the problem a bit further, lead to the conclusion that the optimal solution must contain more than 15 primes. We used this aquired info to direct our algorithem to look for the answer in that area, by modifying the fitness function.

Genome representation: Our genotypes were represented by a bit array sized as the number of primes below 100. when a bit is turned on, his correlating prime number is present in the phenotype.

Results:

• 437 problem: the algorithm found several answers, containing 7 primes. for example:
  (19, 41, 71, 73, 83, 89, 97)
  (3, 61, 71, 73, 79, 89, 97)
• 13782 problem (bonus): the algorithm found several answers, containing 16 primes. for example:
  (569, 719, 727, 769, 811, 821, 857, 859, 881, 919, 941, 967, 971, 983, 991, 997)
  (587, 673, 691, 797, 811, 859, 881, 887, 907, 911, 919, 941, 967, 971, 983, 997)

Conclusions: evolution seems to work well, especially comparing to brute force methods.
We did manage to build a much faster deterministic algorithm (which searches for all possible 16 sized groups, starting from the biggest primes).
This algorithm was specific for these numbers, and would only work if the size of the smallest group is known. The GA however, is more general and needs less pre-calculated data.