EA Research

AIM:

Consolidate understanding of EA and begin design for implementation.

CONDUCT:

  • Read through large part of Introduction to Evolutionary Computing, (Eiben and Smith)
  • Developed EA design considerations
  • Researched EA suitability for problems with small chromosomes

RESULTS:

Developing understanding of practical implementation considerations for EA.

EA design questions are developing as follows:

  • Mutation is largely random (array indexes) so no requirement to modify mutation probability or range based on historical child improvement percentage — OR do we want to do this as there will be SOME general correlation between index position and local maxima???

BREEDING

  • Which percentage of genomes are suitable parents?
  • How are parents chosen and paired from suitable candidates
    • These have percentage to mate or remain
    • Do parents remain in gene pool after mating?

MUTATING

  • Each element has mutation chance?
  • Each element has entire genome iterated over with small mutation chance
  • Only children have mutation chance?
    • IF SO INCORPRATE INTO ABOVE PHASE
      CULLING
  • population = nextGeneration(0,popsize) — nextGeneration is the full SORTED list of candidates for next generation
    • Anything below the number allowed gets killed off

SOLUTION ASSESSMENT

  • Check best candidate (ie. top of population)
    • Store/visualise it?
  • Termination criteria met? (delta change? generations? score threshold?)

GA Design

GeneticAlgorithm Class
Population stored as SortedList:

  • .add(Fitness(genome), genome)
    • Maintains a sorted list of the population

Fitness(Genome) — return fitness function value for that genome

Solution Class

  • Data class for solution

Genome Class

  • bool[] genes
  • Genome()
    • Randomise genes
  • ToSolution()
    • Returns the decoded solution from the genome
  • static Genome FromSolution(Solution s)
    • Create new genome from a solution instead of normal constructor

TIME SPENT:

9 hours (87 hours running total)

DISCUSSION:

Concern regarding suitability of EA as a suitable optimisation process for this problem. The chromosome currently is two integers (indexes of FUP candidate and SBF candidate). While researching EAs it has been mentioned frequently that an EA isnt the most suitable optimisation technique for problems with few variables (where the chromosome is small). This reinforces my concern about a small chromosome in that crossover is very restricted (especially in the extreme case of a two element chromosome) and it may be difficult to maintain the required diversity.

The two integer chromosome could be represented by the respective binary value which would increase the chromosome to a much longer length (although this would be variable depending on size of relevant arrays and introduce non viable solutions where the bit size representation for the largest index would have a max value larger than the index) however I have concerns that EA is the hammer in the toolkit and we are trying to make the problem a nail.

The additional concern I have is it is how effective the EA will be due to the discontinuous nature of the search space; notably that close proximity in the index positions of the candidate FUP/SBF do not directly translate to how close the fitness function will be. This is due to the spacial links between candidates not being preserved in the array representation. (And ties in to the point below re: a graph representation possibly being a better option for candidate storage)

This is something I need to discuss with supervisors and identify alternatives asap. Even if we go with an EA, researching alternatives in detail remains a productive enterprise as it will inform justification for proceeding with an EA in the final report.

Future Improvements thoughts:

  • Implement graph representation of candidate FUP/SBF locations IOT preserve spacial links and allow more effective mutation
  • Tournament selection with ANN trained in comparing two plans as selector
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s