The Design Problem







Description:

      The Design Problem  is a optimization problem that must be solved within the Interactive Evolutionary Computation framework. Originaly this problem was defined for the design of tables, but the problem has been generalized [BEN99].

Within this framework of Interactive Evolutionary Computation (IEC), when working with small populations, the main problem encountered is that the explicit fitness is necessary given by the user through a subjective evaluation to each individual. Therefore, it is rather complicated to find any dependency between the implicit fitness measure and the user decisions. When trying to measure the performance and the behaviour of these kinds of algorithms, the problem is that the user decisions are unpredictable, and they do not depend on the implicit fitness. 
     Formally, this problem can be described as finding an optimal design in no more than 20 iterations with only 10 individuals. The evaluation is made by the user.

  • Chromosome: [C1..CN]
  • Genes: [G1..Gi]

Click here to get this description in tex format and here to get the figure in eps format.








The evolutionary computation paradigm is a group of stochastic learning techniques that use computational models that follow a biological evolution metaphor. In these techniques a population of individuals (solutions) evolve until the convergence criterion is reached, usually until finding a near optimal solution. The problem to solve is how to determine which steps of the genetic algorithm (GA), like population size, selection type, crossover operator, mutation operator, encoding strategy, etc., are better for typically Interactive Evolutionary Computation (IEC) problems.

Population sizes used for genetic algorithms are usually fairly large (100 to 1000 or more) to allow searching through all the solution space, and to avoid local optima. At each generation, many individuals survive and reproduce to create a new offspring. However, when the success of a solution depends on human opinion, then, it is said that there is no global optimum, but many local optima are potentially interesting solutions. For this reason, and also because the user interface must be simple, a smaller population size is needed. In other works, [Sim91], the small population concept has around 20-40 individuals.

Instances and best known solutions for those instances:

      The problem can be instanced for designs of tables [SAE04], logotypes, car, and such on [BER01]. The number of chromosome (N) and genes (i) depends on the user and the problem.






Related Papers:

[BEN99] Bentley P. From Coffee Tables to Hospitals: Generic Evolutionary Design, Evolutionary design by computers, Morgan-Kauffman, pp. 405-423. (1999)

[SIM91] Sims K., Artificial Evolution for Computer Graphics, Comp. Graphics,Vol. 25, 4, pp. 319-328. (1991)

[BER01] Berlanga A., Isasi P. Segovia J. Interactive Evolutionary Computation with Small Population to Generate Gestures in Avatars, Proceedings of the Genetic and Evolutionary Computation, Artificial Life, Adaptative Behavior, and agents. (2001)

[SAE03] Sáez Y., Sanjuán O., Segovia J., Isasi P., Genetic Algorithms for the Generation of Models with Micropopulations, Proc. of the EUROGP'03, Univ. of Essex , UK . Apr. (2003)

Click here to get the bibliography in bibtex fotmat.






Last Updated: 2 10/27/04                                                                                 For any question or suggestion, click here to contact with us.