Что такое хорошие примеры генетических алгоритмов / генетических решений для программирования? [закрытый]

Не знаю, считается ли домашнее задание ...

Во время учебы мы развернули нашу собственную программу для решения задачи коммивояжера.

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

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

Это был интересный курс, поскольку мы также баловались нейронными сетями и тому подобным.

Я»Я хотел бы знать, использовал ли кто-нибудь такой вид программирования в «производственном» коде.

А также некоторые из распространенных проблем, такие как "Коммивояжер" и вариант Роджер Программа Alsing Мона Лиза , я также написал эволюционный решатель судоку (который требовал с моей стороны немного более оригинальной мысли, а не просто повторной реализации чьей-то идеи). Существуют более надежные алгоритмы решения судоку, но эволюционный подход работает довольно хорошо.

В последние несколько дней я экспериментировал с эволюционной программой, чтобы найти «холодные колоды» для покера после просмотра этой статьи на Reddit. На данный момент это не совсем удовлетворительно, но я думаю, что смогу его улучшить.

У меня есть моя собственная структура , которую я использую для эволюционных алгоритмов.

Часто бывает сложно получить точную цветовую комбинацию, когда вы планируете покрасить свой дом. Часто вы имеете в виду какой-то цвет, но это не один из цветов, который вам показывает продавец.

Вчера мой профессор, который является исследователем ГА, упомянул правдивую историю в Германии (извините, у меня нет дополнительных ссылок, да, я могу узнать это, если кто-то попросит). Этот парень (давай я называю его цветным парнем ), который ходил от двери до двери, чтобы помочь людям найти точный цветовой код (в RGB ), который будет шкафом для того, что покупатель имел в разум. Вот как он это делал:

цветной парень имел обыкновение носить с собой программу, которая использовала GA. Раньше он начинал с 4 разных цветов, каждый из которых закодирован как кодированная хромосома (декодированное значение которой было бы значением RGB). Потребитель выбирает 1 из 4 цветов (наиболее близкий к тому, что он / она имеет в виду). Затем программа назначит максимальную приспособленность этому индивиду и перейдет к следующему поколению , используя мутацию / кроссовер . Вышеупомянутые шаги будут повторяться до тех пор, пока потребитель не найдет точный цвет, а затем парень расскажет ему комбинацию RGB!

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

Теперь, когда у меня -1, если вы планируете получить больше -1, пожалуйста. объясните причину этого!

На codechef.com было соревнование (кстати, отличный сайт, ежемесячные соревнования по программированию), где каждый должен был решить неразрешимую судоку (нужно подходить как можно ближе с минимальным количеством ошибок. столбцы / строки / и т. д., насколько это возможно).

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

Я не мог придумать детерминированный подход в этом случае, потому что судоку был размером 300x300, и поиск занял бы слишком много времени.

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

Я использовал Perl и все кодировал сам. Сегодня я бы поступил иначе.

Прочитав Слепой часовщик , я был заинтересован в программе Паскаля, которую Докинз разработал для создания моделей организмов, которые могут со временем развиваться. Я был достаточно заинтересован, чтобы написать свой собственный, используя Swarm . Я не рисовал всю его причудливую графику с животными, но мои «хромосомы» управляли чертами, которые влияли на способность организмов выживать. Они жили в простом мире и могли противопоставить его друг другу и своему окружению.

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

Во-первых, "Генетическое программирование" Джонатана Коза ( на amazon ) в значительной степени ЭТО книга по генетическим и эволюционным алгоритмам / методам программирования с множеством примеров. Я настоятельно рекомендую проверить это.

Что касается моего собственного использования генетического алгоритма, я использовал (выращенный в домашних условиях) генетический алгоритм для разработки алгоритма роя для сценария сбора / уничтожения объектов (практической целью могла быть очистка минного поля ). Вот ссылка на статью . Самой интересной частью того, что я сделал, была многоэтапная функция приспособленности, которая была необходима, поскольку простые функции приспособленности не обеспечивали достаточной информации для генетического алгоритма, чтобы в достаточной степени различать членов популяции.

Футбольные чаевые. Я построил систему GA для прогнозирования результатов игр в AFL (Aussie Rules Football) от недели к неделе.

Несколько лет назад мне надоел стандартный рабочий футбольный пул, все просто выходили в интернет и выбирали из какой-то эксперт из прессы. Итак, я подумал, что не может быть слишком сложно победить кучу специалистов по телевещательной журналистике, верно? Моей первой мыслью было взять результаты из Massey Ratings , а затем раскрыть в конце сезона мою стратегию после завоевания славы и славы. Однако по причинам, которые я никогда не обнаружил, Месси не отслеживает AFL. Циник во мне считает, что это связано с тем, что исход каждой игры AFL в основном становится случайным. но мои жалобы на недавние изменения правил относятся к другому форуму.

Система в основном учитывала силу атаки, силу защиты, преимущество домашнего поля, еженедельное улучшение (или его отсутствие) и скорость изменений каждого из них. Это создало набор полиномиальных уравнений для каждой команды за сезон. Можно было вычислить победителя и счет для каждого матча на заданную дату. Цель состояла в том, чтобы найти набор коэффициентов, который наиболее точно соответствовал исходу всех прошлых игр, и использовать этот набор для прогнозирования предстоящей игры недели.

На практике система находила бы решения, которые точно предсказывали более 90% прошлой игры. результаты. Затем он успешно выберет около 60-80% игр на предстоящую неделю (это неделя, не входящая в тренировочный набор).

Результат: чуть выше середины пакета. Ни крупного денежного приза, ни системы, которую я мог бы использовать, чтобы обыграть Вегас. Хотя это было весело.

Я построил все с нуля, без фреймворка.

Пару недель назад я предложил решение для SO , использующее генетические алгоритмы для решения проблемы компоновки графов. Это пример задачи оптимизации с ограничениями.

Также в области машинного обучения я с нуля реализовал структуру правил классификации на основе GA на c / c ++.
Я также использовал GA в демонстрационном проекте для обучения искусственных нейронных сетей (ANN) в отличие от использования известного алгоритма обратного распространения ошибки .

Кроме того, и как часть моей В своих дипломных исследованиях я использовал GA в обучении Скрытые марковские модели в качестве дополнительного подхода к основанному на EM алгоритму Баума-Велча (снова на c / c ++).

Я использовал простой генетический алгоритм для оптимизации отношения сигнал / шум волны, представленной в виде двоичной строки. Перевернув биты определенным образом на протяжении нескольких миллионов поколений, я смог произвести преобразование, которое привело к более высокому отношению сигнал / шум этой волны. Алгоритм также мог быть «Simulated Annealing», но в данном случае он не использовался. По своей сути, генетические алгоритмы просты, и это был примерно такой же простой вариант использования, который я видел, поэтому я не использовал структуру для создания и выбора генерации - только случайное начальное значение и отношение сигнал / шум. функция под рукой.

I used a GA to optimize seating assignments at my wedding reception. 80 guests over 10 tables. Evaluation function was based on keeping people with their dates, putting people with something in common together, and keeping people with extreme opposite views at separate tables.

I ran it several times. Each time, I got nine good tables, and one with all the odd balls. In the end, my wife did the seating assignments.

My traveling salesman optimizer used a novel mapping of chromosome to itinerary, which made it trivial to breed and mutate the chromosomes without any risk of generating invalid tours.

Update: Because a couple people have asked how ...

Start with an array of guests (or cities) in some arbitrary but consistent ordering, e.g., alphabetized. Call this the reference solution. Think of a guest's index as his/her seat number.

Instead of trying to encode this ordering directly in the chromosome, we encode instructions for transforming the reference solution into a new solution. Specifically, we treat the chromosomes as lists of indexes in the array to swap. To get decode a chromosome, we start with the reference solution and apply all the swaps indicated by the chromosome. Swapping two entries in the array always results in a valid solution: every guest (or city) still appears exactly once.

Thus chromosomes can be randomly generated, mutated, and crossed with others and will always produce a valid solution.

На семинаре в школе мы разрабатываем приложение для создания музыки в музыкальном режиме. Программа была построена на Java, и на выходе получился midi-файл с песней. Мы используем различные подходы GA для создания музыки. Думаю, эта программа может быть полезна для изучения новых композиций.

В рамках моей степени бакалавра CompSci нам была поставлена ​​задача поиска оптимальных флагов jvm для исследовательской виртуальной машины Jikes. Это было оценено с помощью набора тестов Dicappo, который возвращает время на консоль. Я написал распределенный мягкий алгоритм, который переключает эти флаги, чтобы улучшить время выполнения набора тестов, хотя для компенсации аппаратного джиттера, влияющего на результаты, потребовались дни. Единственная проблема заключалась в том, что я плохо разбирался в теории компилятора (что и было целью задания).

At work I had the following problem: given M tasks and N DSPs, what was the best way to assign tasks to DSPs? "Best" was defined as "minimizing the load of the most loaded DSP". There were different types of tasks, and various task types had various performance ramifications depending on where they were assigned, so I encoded the set of job-to-DSP assignments as a "DNA string" and then used a genetic algorithm to "breed" the best assignment string I could.

It worked fairly well (much better than my previous method, which was to evaluate every possible combination... on non-trivial problem sizes, it would have taken years to complete!), the only problem was that there was no way to tell if the optimal solution had been reached or not. You could only decide if the current "best effort" was good enough, or let it run longer to see if it could do better.

Мы с коллегой работаем над решением для погрузки грузов на грузовики с использованием различных критериев, которые требует наша компания. Я работал над решением генетического алгоритма, в то время как он использовал Branch And Bound с агрессивной обрезкой. Мы все еще находимся в процессе внедрения этого решения, но до сих пор добиваемся хороших результатов.

Я использовал генетические алгоритмы (а также некоторые связанные с ними методы), чтобы определить наилучшие настройки для системы управления рисками, которая пыталась удержать золотодобывающих фермеров от использования украденных кредитных карт для оплаты MMO. Система обрабатывала несколько тысяч транзакций с «известными» значениями (мошенничество или нет) и выясняла, какое сочетание настроек было бы наилучшим, чтобы правильно идентифицировать мошеннические транзакции без слишком большого количества ложных срабатываний.

У нас были данные о нескольких десятках (логические) характеристики транзакции, каждой из которых было присвоено значение и суммировано. Если сумма была выше порогового значения, транзакция была мошенничеством. GA создаст большое количество случайных наборов значений, оценит их по совокупности известных данных, выберите те, которые набрали наибольшее количество баллов (как по выявлению мошенничества, так и по ограничению количества ложных срабатываний), затем скрестите несколько лучших из каждого поколения, чтобы получить новое поколение кандидатов. Через определенное количество поколений лучший набор значений считался победителем.

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

выявление подавляющего большинства случаев мошенничества, которое имело место, но не удалось снизить уровень ниже 1% для наиболее подверженных мошенничеству элементов (учитывая, что 90% входящих транзакций могут быть мошенничеством

Я сделал все это с помощью perl. Один запуск программного обеспечения на довольно старом Linux-компьютере займет 1-2 часа (20 минут для загрузки данных по WAN-каналу, остальное время потрачено на обработку). Размер любого данного поколения ограничивался доступной оперативной памятью. Я повторял его снова и снова, с небольшими изменениями параметров, в поисках особенно хорошего набора результатов.

В целом он позволил избежать некоторых оплошностей, которые возникали при попытке вручную настроить относительные значения десятков индикаторов мошенничества. , и постоянно приходил к лучшим решениям, чем я мог создать вручную. AFAIK, он все еще используется (примерно через 3 года после того, как я его написал).

остальное время потратил на хруст). Размер любого данного поколения ограничивался доступной оперативной памятью. Я повторял его снова и снова, с небольшими изменениями параметров, в поисках особенно хорошего набора результатов.

В целом он позволил избежать некоторых оплошностей, которые возникали при попытке вручную настроить относительные значения десятков индикаторов мошенничества. , и постоянно приходил к лучшим решениям, чем я мог создать вручную. AFAIK, он все еще используется (примерно через 3 года после того, как я его написал).

остальное время потратил на хруст). Размер любого данного поколения ограничивался доступной оперативной памятью. Я пробегал его снова и снова, с небольшими изменениями параметров, в поисках особенно хорошего набора результатов.

В целом, он позволил избежать некоторых ошибок, которые возникали при попытке вручную настроить относительные значения десятков индикаторов мошенничества. , и постоянно приходил к лучшим решениям, чем я мог создать вручную. AFAIK, он все еще используется (примерно через 3 года после того, как я его написал).

и постоянно приходил к лучшим решениям, чем я мог создать вручную. AFAIK, он все еще используется (примерно через 3 года после того, как я его написал).

и постоянно приходил к лучшим решениям, чем я мог создать вручную. AFAIK, он все еще используется (примерно через 3 года после того, как я его написал).

How much faster is it

Define 'faster'. Do you mean HTTP performance (see below) or rendering performance?

You no longer gain the benefit of caching

Actually, if you're doing this in a CSS file it will still be cached. Of course, any changes to the CSS will invalidate the cache.

In some situations this could be used as a huge performance boost over many HTTP connections. I say some situations because you can likely take advantage of techniques like image sprites for most stuff, but it's always good to have another tool in your arsenal!

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

Затем я решил провести небольшой эксперимент. Я дал мозгу существа выходной нейрон под названием «рот» и входной нейрон под названием «ухо». Начал заново и был удивлен, обнаружив, что они эволюционировали, чтобы максимизировать пространство, и каждое соответствующее существо останется в своей части (еда была размещена случайным образом). Они научились сотрудничать друг с другом и не мешать друг другу. Всегда были исключения.

Потом я попробовал кое-что интересное. Я мертвые существа стали бы пищей. Попробуйте угадать, что случилось! Появились два типа существ: те, которые атаковали, как стаи, и те, которые хорошо избегали.

Итак, какой урок здесь? Общение - это сотрудничество. Как только вы вводите элемент, в котором причинение вреда другому означает, что вы что-то получаете, сотрудничество разрушается.

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

Edit:

Я написал его на C ++ без использования фреймворков. Написал собственную нейронную сеть и код GA. Эрик, спасибо, что сказал, что это правдоподобно. Обычно люди не верят в возможности GA (хотя ограничения очевидны), пока не поиграют с ней. GA прост, но не упрощен.

Для сомневающихся доказано, что нейронные сети могут моделировать любую функцию, если они имеют более одного слоя. GA - довольно простой способ перемещаться по пространству решений, находя локальный и потенциально глобальный минимум. Объедините GA с нейронными сетями, и вы получите довольно хороший способ найти функции, которые находят приблизительные решения для общих проблем. Поскольку мы используем нейронные сети, мы оптимизируем функцию для некоторых входных данных, а не для некоторых входных данных функции, поскольку другие используют GA

Вот демонстрационный код для примера выживания: http: // www. mempko.com/darcs/neural/demos/eaters/ Инструкции по сборке:

• Установите darcs, libboost, liballegro, gcc, cmake, make
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake.
• make
• cd demos / eaters
• ./ eaters

Я создал полную структуру GA под названием «GALAB», чтобы решить множество проблем:

• определение местоположения GSM ANT (BTS) для уменьшения перекрытия и пустых местоположений.
• Планирование проекта при ограниченных ресурсах.
• Эволюционное создание картины. ( Evopic )
• Задача коммивояжера.
• Проблемы N-Queen и N-Color.
• Рыцарский тур и задачи о ранце.
• Магический квадрат и судоку.
• сжатие строк, основанное на задаче Superstring.
• Проблема с 2D-упаковкой.
• Крошечное приложение для искусственной жизни.
• Загадка Рубика.