The Quadratic Knapsack Problem extends the 0-1 Knapsack Problem by associating values not only with individual objects but also with pairs of objects. Two genetic algorithms encode candidate solutions to this problem ...
详细信息
ISBN:
(纸本)9781450311786
The Quadratic Knapsack Problem extends the 0-1 Knapsack Problem by associating values not only with individual objects but also with pairs of objects. Two genetic algorithms encode candidate solutions to this problem as permutations of objects. One GA applies no heuristic steps while a second seeds its population and performs crossover by considering the values of objects relative to the objects already in the knapsack. Both algorithms perform well, and competitively with two earlier binary-coded GAs. The heuristic measures improve performance significantly.
Keyboard design is a combinatorial problem of perennial interest to those who work with computers. An evolutionary algorithm can search a space of key arrangements for one that is easy to use. Its genotypes represent ...
详细信息
ISBN:
(纸本)9781581139648
Keyboard design is a combinatorial problem of perennial interest to those who work with computers. An evolutionary algorithm can search a space of key arrangements for one that is easy to use. Its genotypes represent candidate keyboards, and its fitness function measures the difficulty of typing a specified body of text. Here, a genetic algorithm seeks to arrange the twenty-six letter and six punctuation marks (four of the latter in two pairs) on three rows of ten keys each. It encodes keyboards as permutations of key positions. Its evaluation function considers the relative loads on the hands, consecutive keystrokes by one hand or finger, and the relative difficulties of using individual fingers as it simulates typing a block of text. In tests using a concatenated body of text and its three components (a collection of message logs, Moby Dick, and the King James Bible), the GA consistently evolved keyboards with markedly better evaluations than either the QWERTY or Dvorak keyboards, though the GA's keyboards differed depending on the text it used in its evaluation function.
暂无评论