Решение задачи коммивояжера
Задача коммивояжера является классической оптимизационной задачей. Суть ее заключается в следующем. Дано множество из п городов и матрица расстояний между ними или стоимостей переезда. Цель коммивояжера – объехать все эти города по кратчайшему пути или с наименьшими затратами на поездку. Причем в каждом городе он должен побывать один раз и свой путь закончить в том же городе, откуда начал. Рассмотрим конкретный пример. Пусть имеется пять городов, стоимость переезда между которыми определяется следующей матрицей: 0 4 6 2 9 4 0 3 2 9 6 3 0 5 9 2 2 5 0 8 9 9 9 8 0 Для решения задачи применим следующий генетический алгоритм. Решение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения городов. А значение целевой функции будет равно стоимости всей поездки, вычисленной в соответствии с вышеприведенной матрицей. Сразу заметим, что одним из оптимальных решений задачи является последовательность 514235 стоимостью 25. В качестве оператора отбора будем использовать традиционный оператор, применявшийся в предыдущем примере. При этом заметим, что чем меньше значение целевой функции, тем лучше. То есть целью в данном случае является поиск минимума целевой функции. В качестве оператора скрещивания выберем более изощренную процедуру, похожую на двухточечный оператор скрещивания. Поясним его работу на примере. Пусть есть две родительские перестановки (12345) и (34521). Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка – между четвертым и пятым: (1 | 234 | 5), (3 | 452 | 1). На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (* |452| *), (* |234| *). На втором этапе вместо звездочек вставляются соответствующие числа из исходной родительской перестановки, начиная со второго числа выделенного фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в первой перестановке (1|234|5) таким начальным числом является 3, за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1. В итоге вместо (* |452| *) получаем (34521), аналогично из (3|452|1) и (* |234| *) получаем (52341). Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному закону. Вероятность мутации 0,01. Размер популяции выберем равным 4. Исходная популяция представлена в таблице 7.6. Табл. 7.6. Исходная популяция особей
Пусть для скрещивания были выбраны следующие пары: (1, 3) и (2, 4). В результате были получены потомки, представленные в таблице 7.7. Табл. 7.7. Родители и потомки на первой итерации
Пусть для потомка (12354) сработал оператор мутации, и обменялись местами числа 2 и 3. В данном случае строка (12354) изменилась на значение (13254). Популяция первого поколения после отсечения худших особей в результате операции редукции приняла вид, представленный в таблице 7.8. Табл. 7.8. Популяция первого поколения
Пусть для получения второго поколения выбраны следующие пары строк: (1, 4) и (2, 3). И в результате получены потомки, показанные в таблице 7.9. Табл. 7.9. Родители и потомки на второй итерации
Популяция второго поколения после отсечения худших особей приняла вид, показанный в таблице 7.10. Табл. 7.10. Популяция второго поколения
Таким образом, после двух итераций значение целевой функции изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75, а общее качество с 122 до 111. Произошло пусть незначительное, но улучшение популяции.
|
