Дилемма заключенных.
Два заключенных содержатся в отдельных камерах и не могут общаться друг с другом. Каждый заключенный на допросе может выдать или не выдать другого. Если только один заключенный выдает другого, он награждается, а другой наказывается. Если оба выдают друг друга, они оба наказываются и подвергаются пыткам. Если никто не выдал друг друга, оба умеренно награждаются. С точки зрения индивидуального заключенного, ему выгоднее все время выдавать другого заключенного, за это он будет получать больше, чем если оба будут молчать. Но ведь другой заключенный думает так же. А если оба выдают друг друга, оба будут наказаны. В этом и заключается дилемма заключенных - определить стратегию поведения в такой ситуации. Эта дилемма может быть представлена как игра между двумя игроками, где за каждый ход каждому игроку предстоит решить, выдавать или не выдавать оппонента. В конце хода игроки знакомятся с ответом оппонента и получают за ответ очки:
Дилемма заключенных
Таблица 1. Дилемма заключенных.
Решение дилеммы с помощью ГА.
Прежде всего, необходимо как-то представить стратегию (т.е. возможное решение). Достаточно при приеме решения учитывать решения и ответы за три предыдущих хода. Таким образом, с четырьмя возможными вариантами ответов за каждый ход, имеем 4*4*4 = 64 варианта хромосомы (вида трех предыдущих ходов). Стратегия в таком случае может быть представлена с помощью перебора всех возможных ситуаций (показывающих действия за предыдущие три хода) и указания, какой ход необходимо сделать сейчас. Таким образом, стратегия может быть представлена строкой из 64 битов. Допустим, строка начинается с битов
(1 0 1 …), (1-не выдавать, 0-выдавать). Это означает:
· если предыдущие три хода были - выдавать всех (0,0 0,0 0,0), то не выдавать.
· Если предыдущие три хода были: (0,0 0,0 0,1), то выдавать.
· Если предыдущие три хода были: (0,0 0,0 1,0), то не выдавать.
И т.д.
Чтобы представить стратегию, которая была в самом начале игры, необходимо еще 6 битов. Таким образом всего хромосома будет содержать 70 битов.
Строка из семидесяти битов определяет, что игрок будет делать в различных ситуациях и полностью определяет индивидуальную стратегию. Строка из семидесяти битов также подходит для хромосомы игрока при использовании в эволюционном процессе.
Генетический алгоритм Аксельрода (Axelrod) для разработки стратегии дилеммы заключенных работает в 4 стадии:
· Выбор начальной популяции. Каждому игроку присваивается случайным образом заполненная строка из семидесяти бит, представляющих стратегию.
· Тест каждого игрока, чтобы определить ее эффективность. Каждый игрок использует стратегию, записанную в его хромосоме при игре с другими игроками. Очки игрока - сумма всех очков, полученных во всех играх. Игроки с максимальным количеством очков допускаются к дальнейшей игре.
· Выбор игроков для размножения. Выбирают игроков с количеством очков выше среднего и разрешают им спариваться. Игрокам со средним количеством очков разрешено одно спаривание, с очками выше среднего - два. Игроки с количеством очков ниже среднего не спариваются.
· Все игроки, получившие разрешение на спаривание, случайным образом скрещиваются, от них получается по два потомка. Это делается, используя два генетических оператора: кроссовер и мутация.
После этих четырех стадий мы получаем новую популяцию. Члены этой популяции могут быть очень не похожими друг на друга, но количество очков у них будет приблизительно одинаковым. С каждой новой итерацией среднее количество очков будет повышаться, а состав популяции будет становиться все более похожим.
Итоги работы:
В результате работы было представлено несколько стратегий с максимальным количеством очков. Вот они:
· "Не шатайте лодку": продолжать кооперацию (1,1 1,1 1,1)
· "Провокатор": после установления кооперации предать (1,1 1,1 1,0)
· "Зуб за зуб, глаз за глаз": отвечать противнику тем же, что он сделал перед этим (1,0 0,1 1,1)
· "Простить грехи: забыть об обиде (0,1 1,1 1,1)
· "Кровная месть": несотрудничество (0,0 0,0 0,0)
