Создание моего первого алгоритма

Question

Эй, ребята, вернулись снова с совершенно новым проектом для себя. В моих предыдущих постах я привык к программированию, чтобы выполнять определенные работы было довольно легко, но теперь я хочу посмотреть, что можно сделать в программировании чего-то более творческого.

Поэтому я буду задавать ряд вопросов, связанных с алгоритмами. Не имейте Скуби, кто они на самом деле или как их написать. Но меня интересует GA(генетические алгоритмы).

Я сломал то, что я попытаюсь достичь, но мне нужна стартовая точка и немного программирования (консоль C#), чтобы заставить меня двигаться дальше и мыслить программно. Надеюсь, вам понравится читать и может помочь мне в моем пути.

Все живые организмы состоят из клеток. В каждой клетке есть одинаковый набор хромосом. Хромосомы являются нитями ДНК и служат моделью для всего организма. Хромосома состоит из генов, блоков ДНК. Каждый ген кодирует определенный белок. В основном можно сказать, что каждый ген кодирует признак, например цвет глаз. Возможные настройки для признака (например, синий, коричневый) называются аллелями. Каждый ген имеет свою позицию в хромосоме. Эта позиция называется локусом.

Полный набор генетического материала (все хромосомы) называется геном. Конкретный набор генов в геноме называется генотипом. Генотип с последующим развитием после рождения является основой для фенотипа организма, его физических и психических характеристик, таких как цвет глаз, интеллект и т. Д.

Схема основного генетического алгоритма

1. [Начало] Генерация случайной популяции из n хромосом (подходящие решения для проблемы)
2. [Пригодность] Оцените пригодность f(x) каждой хромосомы x в популяции
3. [Новая популяция] Создайте новую популяцию, повторяя следующие шаги до тех пор, пока новая популяция не будет завершена 1. [Выбор] Выберите две родительские хромосомы из популяции в соответствии с их пригодностью (чем лучше приспособленность, тем больше шансов быть выбранной) 2. [Кроссовер ] С вероятностью пересечения пересекают родителей, чтобы сформировать новое потомство (детей). Если кроссовер не проводился, потомок является точной копией родителей. 3. [Мутация] С вероятностью мутации мутировать нового потомства в каждом локусе (положение в хромосоме). 4. [Принятие] Поместить нового потомства в новую популяцию
4. [Заменить] Использовать новую сгенерированную популяцию для дальнейшего запуска алгоритма
5. [Тест] Если конечное условие удовлетворено, остановите и верните лучшее решение в текущей совокупности
6. [Петля] Перейти к шагу 2

Кодирование хромосомы

Хромосома должна каким-то образом содержать информацию о растворе, который она представляет. Наиболее используемый способ кодирования - это двоичная строка. Тогда хромосома может выглядеть так:

Chromosome 1    1101100100110110
Chromosome 2    1101111000011110

Каждая хромосома имеет одну двоичную строку. Каждый бит в этой строке может представлять некоторую характеристику решения. Или вся строка может представлять число - это было использовано в базовом апплете GA.

Конечно, есть много других способов кодирования. Это зависит в основном от решаемой проблемы. Например, можно кодировать непосредственно целые или действительные числа, иногда полезно кодировать некоторые перестановки и так далее.

Кроссовер

После того, как мы решили, какую кодировку мы будем использовать, мы можем сделать шаг к переходу. Кроссовер отбирает гены из родительских хромосом и создает нового потомства. Самый простой способ сделать это состоит в том, чтобы случайным образом выбрать некоторую точку пересечения и все, что находится до этой точки, скопировать из первого родителя, а затем все после копии точки пересечения из второго родителя.

Кроссовер может выглядеть следующим образом ( | это точка кроссовера):

Chromosome 1    11011 | 00100110110
Chromosome 2    11011 | 11000011110
Offspring 1     11011 | 11000011110
Offspring 2     11011 | 00100110110

Есть и другие способы, как сделать кроссовер, например, мы можем выбрать больше точек кроссовера. Кроссовер может быть довольно сложным и очень зависит от кодирования кодирования хромосомы. Конкретный кроссовер, созданный для конкретной задачи, может улучшить производительность генетического алгоритма.

перегласовка

После выполнения кроссовера происходит мутация. Это сделано для предотвращения попадания всех решений населения в локальный оптимум решаемой проблемы. Мутация меняет случайным образом нового потомства. Для двоичного кодирования мы можем переключить несколько случайно выбранных битов от 1 до 0 или от 0 до 1. Тогда мутация может быть следующей:

Original offspring 1    1101111000011110
Original offspring 2    1101100100110110
Mutated offspring 1     1100111000011110
Mutated offspring 2     1101101100110110

Мутация зависит как от кодировки, так и от кроссовера. Например, когда мы кодируем перестановки, мутация может обмениваться двумя генами.

Answer 1

Посмотрите на ваше объяснение.

Схема основного генетического алгоритма

1. [Начало] Генерация случайной популяции из n хромосом (подходящие решения для проблемы)
2. [Пригодность] Оцените пригодность f(x) каждой хромосомы x в популяции
3. [Новая популяция] Создайте новую популяцию, повторяя следующие шаги, пока новая популяция не будет завершена
   1. [Выбор] Выберите две родительские хромосомы из популяции в зависимости от их пригодности (чем лучше приспособленность, тем больше шансов быть выбранным)
   2. [Кроссовер] С вероятностью кроссовера пересекают родителей, чтобы сформировать новое потомство (детей). Если кроссовер не проводился, потомок является точной копией родителей.
   3. [Мутация] С вероятностью мутации мутировать новое потомство в каждом локусе (положение в хромосоме).
   4. [Принятие] Поместите нового потомства в новую популяцию
4. [Заменить] Использовать новую сгенерированную популяцию для дальнейшего запуска алгоритма
5. [Тест] Если конечное условие удовлетворено, остановите и верните лучшее решение в текущей совокупности
6. [Петля] Перейти к шагу 2

Это уже очень похоже на программу. Если вы возьмете это и преобразуете в код, вам нужно пройти около 95% пути. Чего вам не хватит, так это вашей "фитнес-функции", которая, по сути, представляет собой решение + критерии успеха. Это зависит от вопроса, поэтому мы не можем помочь здесь. Но то, что он сделал бы, это более чем вероятно, использовать биты хромосомы в качестве флагов или кодов операций, в зависимости от сложности проблемы, и посмотреть, как быстро и как быстро хромосома (то есть: текущая комбинация битов / байтов / флагов / коды операций / что угодно) решил проблему.