X. Кодиране
Въведение
Кодирането на хромозомите е един от проблемите, когато се започне решаване на проблем с GA. Кодирането много зависи от проблема.
В тази глава ще бъдат представени някои кодирания, които бяха представени с някакъв успех.
Двоично Кодиране
Двоичното кодиране е най-основно, основно защото първите GA са използвали този начин на кодиране.
При двоично кодиране всяка хромозома е низ от битове, 0 или 1.
| Хромозома A | 101100101100101011100101 |
| Хромозома B | 111111100000110000011111 |
Пример за хромозоми с двоично кодиране
Двоичното кодиране дава много възможни хромозоми дори с малък брой алели. От друга страна, това кодиране често не е естествено за много проблеми и понякога трябва да се правят корекции след кръстосването и/или мутацията.
Пример за Проблема: Проблем с раница
Проблемът: Има неща с дадена стойност и размер. Раницата има определен капацитет. Избират се неща така че да се вземе максимален брой, но без разширяване капацитета на раницата.
Кодиране: Всеки бит показва, дали съответното нещо е в раницата.
Кодиране на Пермутации
Кодирането на пермутации може да бъде използвано в проблеми с изброяване, като пътуващият търговец или задачата за подреба на поръчки.
При кодиране на пермутации , всяка хромозома е низ от числа, които представят номера в поредица.
| Хромозома A | 1 5 3 2 6 4 7 9 8 |
| Хромозома B | 8 5 6 7 2 3 1 4 9 |
Пример за хромозоми с кодиране на пермутации
Кодирането на пермутации е полезно само за проблеми с подредба. Дори за този проблем за някои типове кръстосване и мутация трябва да се направят корекции за да остане хромозомата плътна (т.е. да има реална последователност в нея).
Пример за Проблема: Проблем на търговския пътник (TSP)
Проблемът: Дадени са градове и разстоянията между тях. Търговският пътник трябва да ги посети всичките, но не бива да пътува твърде много. Да се намери последователност от градове, така че да се минимизира дължината на пътя.
Кодиране: Хоромозомата означава подредбата на градовете, по която търговеца ще ги посети.
Кодиране по Стойност
Директното кодиране по стойност може да бъде използвано в проблеми, където се използват някои усложнение стойности, като реални числа. Използването на двоично кодиране при този вид проблеми би било твърде сложно.
При кодиране по стойност , всяка хромозома е низ от някакви стойности. Стойностите могат да бъдат всякакви свързани с проблема, от числа, реални числа или символи, до някакви усложнени обекти.
| Хромозома A | 1.2324 5.3243 0.4556 2.3293 2.4545 |
| Хромозома B | ABDJEIFJDHDIERJFDLDFLFEGT |
| Хромозома C | (back), (back), (right), (forward), (left) |
Пример за хромозома с кодиране по стойност
Кодирането по стойност е много добро за някои специализирани проблеми. От друга страна, за това кодиране често се налага развиване на различно кръстосване и мутация, специфични за проблема.
Пример за Проблема: Намиране на теглата на невронна мрежа
Проблемът: Дадена е някаква невронна мрежа с определена архитектура. Намерете тегла за вход на невроните така че да обучават мрежата за желания изход.
Кодиране: Реални стойности в хромозомата представят съответните тегла за вход.
Кодиране в Дърво
Кодиране в дърво се използва главно динамични програми или изрази, за генетично програмиране.
При кодиране в дърво всяка хромозома е дърво от някакви обекти, като функции или команди в програмен език.
Хромозома A |
Хромозома B |
|
|
( + x ( / 5 y ) ) |
( do_until step wall ) |
Пример за хромозома с кодиране в дърво
Кодирането в дърво е добро за разширяващи се програми. Програмния език LISP е често използван за това, защото програмите на него са представени в тази форма и може лесно да се представят като дърво, така кръстосването и мутацията могат да се извършат о тносително лесно.
Пример за Проблем: Намиране на функция по зададени стойности
Проблемът: Дадени са някакви входни и изходни стойности. Задачата е да се намери функция, която ще даде най-добрия (най-близо до желания) изход за всички входове.
Кодиране: Хромозомата е функцията представена като дърво.
·