Одним из наиболее важных решений, которые необходимо принять при реализации генетического алгоритма, является определение представления, которое мы будем использовать для представления наших решений. Было отмечено, что неправильное представление может привести к плохой производительности ГА.
Следовательно, выбор правильного представления, правильное определение отображений между фенотипом и пространством генотипа имеет важное значение для успеха ГА.
В этом разделе мы представляем некоторые из наиболее часто используемых представлений для генетических алгоритмов. Тем не менее, представление в значительной степени зависит от проблемы, и читатель может обнаружить, что другое представление или сочетание представлений, упомянутых здесь, могут лучше удовлетворить его / ее проблему.
Бинарное Представление
Это одно из самых простых и широко используемых представлений в ГА. В этом типе представления генотип состоит из битовых строк.
Для некоторых задач, когда пространство решений состоит из логических переменных решения — да или нет, двоичное представление является естественным. Возьмем, к примеру, проблему ранца 0/1. Если есть n элементов, мы можем представить решение в виде двоичной строки из n элементов, где x- й элемент сообщает, выбран ли элемент x (1) или нет (0).
Для других задач, в частности тех, которые касаются чисел, мы можем представить числа с их двоичным представлением. Проблема с этим типом кодирования состоит в том, что разные биты имеют разное значение, и поэтому операторы мутации и кроссовера могут иметь нежелательные последствия. Эту проблему можно решить в некоторой степени, используя кодирование Грея, поскольку изменение в один бит не оказывает существенного влияния на решение.
Реальное представление
Для задач, где мы хотим определить гены, используя непрерывные, а не дискретные переменные, реальное представление является наиболее естественным. Точность этих вещественных чисел или чисел с плавающей точкой, однако, ограничена компьютером.
Целочисленное представление
Для дискретных генов мы не всегда можем ограничить пространство решения бинарным «да» или «нет». Например, если мы хотим кодировать четыре расстояния — север, юг, восток и запад, мы можем кодировать их как {0,1,2,3} . В таких случаях желательно целочисленное представление.
Представление перестановки
Во многих задачах решение представлено порядком элементов. В таких случаях представление перестановки является наиболее подходящим.
Классическим примером этого представления является проблема коммивояжера (TSP). При этом продавец должен совершить экскурсию по всем городам, посетить каждый город ровно один раз и вернуться в стартовый город. Общая дистанция тура должна быть минимизирована. Решением этого TSP является, естественно, упорядочение или перестановка всех городов, и поэтому использование перестановочного представления имеет смысл для этой проблемы.