gifts2017

Простой генетический алгоритм в 1С 8

Опубликовал Alex Family (detro) в раздел Программирование - Теория программирования

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

Генетический алгоритм (ГА) можно рассматривать как одну из разновидностей случайного поиска [30], которая основана на механизмах, напоминающих естественный отбор и размножение.

http://matlab.exponenta.ru/fuzzylogic/book5/1_2.php

 

Принцип работы:

Вводим строку, которую необходимо найти с использованием ГА. (без цифр и спец. символов).

Указываем параметры работы. ( параметры прекращения- при указании высокого % совпадения и невозможности его достичь за 1000 проходов, цикл останавливается)

Оценка особей- вычисляется как число правильно отгаданных букв.

 

p.s. алгоритм не оптимизировался, не претендует на образец для подражания

p.s.s. если кто решал похожую задачу на 1С, просьба поделиться :)


Мысли о реализации:

В классической реализации ГА, параметры обычно кодируются двоичной кодировкой или используется код Грея. Применительно к реализации на 1С и решению экономических задач, насколько допустимо использовать в качестве параметров объекты 1С...

Например решаем задачу: N заказов поставщику, Х денег — какие заказы необходимо оплатить для получения макс. прибыли за мин. срок времени.

Тогда хромосома может состоять из Y заказов, и при скрещивании мы будем обмениваться именно заказами.

А целевая функция будет проводить оценку по мин. стоимости и макс. прибыльности заказов в одной хромосоме, с учетом текущего спроса «Заявки покупателей».

 

Скачать файлы

Наименование Файл Версия Размер Кол. Скачив.
ГА_lite.epf
.1239000416 12,91Kb
04.12.14
141
.1239000416 12,91Kb 141 Бесплатно

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Сhe Burashka (CheBurator) 06.04.09 12:11
ну, насколько я себе представляю - ГА отличаются быстрой работой в оптимизационных задачах. В чем дает выигрыш данная разработка?
2. crazy1C (detro) 06.04.09 12:27
Прежде всего это учебная задача, практической пользы нет, мне интересен опыт реализации ГА на 1С. может кто захочет поделиться мыслями, данный вариант моё видение.
Я вижу использование ГА в поиске решений с множеством ограничений. Сейчас не ставил задачу, скорость работы.
3. Федор Программист (fedor40) 06.04.09 14:26
1. Всегда разный результат будет. Клиенту может не понравится.
2. Надо бы сравнить этот метод с методами линейного прог.
4. crazy1C (detro) 06.04.09 14:37
fedor40 06.04.2009 14:26:25
1) Результат очень сильно зависит от начальной популяции, в чем легко убедиться при работе с текущей обработкой.
Для практического применения просто нужно указывать критерии проходимости, если относительно задачи описанной выше, это может быть % дохода на вложенные средства не меньше чем 20% и пока данный результат не достигнут происходит работа ГА.
Так же для повышения качества результатов необходимо параллельно создавать несколько популяций и среди них выбирать наилучшего.
2) Этого добра много в инете, но как правило задачи в которых параметров большое количество решаются с помощью ГА
5. Сергей Дудаков (Anything) 06.04.09 17:52
Самое сложное в генетических алгоритмах - найти задачу, решение которой требовало бы их использование. ;)
6. Федор Программист (fedor40) 06.04.09 19:42
Задачи:

1) закупка товара по количеству, сумме, весу, объему
2) создание цепочки доставки товара
3) загрузка производственного оборудования
7. crazy1C (detro) 07.04.09 09:48
(5)
Задачи, которые можно решить с помощью ГА: транспортная логистика – параметры вес, объём машины, вес, объём точки развоза, ограничение по времени работы, как точки так и машины, продолжительность маршрута, стоимость маршрута и т.д.
Если взять задачу описанную выше:
«N заказов поставщику, Х денег — какие заказы необходимо оплатить для получения макс. прибыли за мин. срок времени», добавим сюда важные параметры как дата поступления на склад, планируемые даты отгрузки, ограничение по кол-ву одного вида товаров и т.д., то сразу видно насколько усложняется задача для реализации.
8. Сергей Дудаков (Anything) 07.04.09 13:51
(6) (7) Да, наверное, эти задачи можно решать с помощью ГА.

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

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

Но чего-то я распессимизничался...

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

Можно по этой теме создать отдельную группу ученых умов и коллективно трудиться на данной задачей.
9. Артем (ArtemK) 08.04.09 08:35
В любом случае реализация методов ИИ на базе 1С - достойное дело. Тем более, что поле применения - широкое, а вот каких-то наработок - как кот наплакал.
10. Crag 08.04.09 12:28
Алгоритм хороший, осмелюсь внести предложение по модернизации):
Отбирать пары для скрещивания можно исходя не только из оценки, но еще методом турнирного отбора. Это позволит избежать появление доминируещего генотипа. Так же можно скрещивать всех со всеми, а потом уже отбирать.
Успехов в реализации!
11. inse0f (inse0f) 08.04.09 13:28
любопытно
жаль только математику 1С считать будет очень медленно в любом случае
поэтому только через ВК, иначе производительность ни к черту

я тестал, надо было обработать 2ух мерный массив размером 640на480
1с один обход делает около 10 секунд,
dll-ка же обработала его за 0.1 секунды с учетом обращении к самой компоненте
12. inse0f (inse0f) 08.04.09 13:28
когда скорость отличается на 2 порядка, это уже о чем то говорит..
13. Максим Богословский (ulen) 08.04.09 18:24
Для увеличения скорости лучше использовать внешнюю компоненту
14. Сhe Burashka (CheBurator) 10.04.09 03:44
почитал.. освежил в памяти... особенно прикололо то, что из бессмысленного набора букв можно быстро получить нужную фразу (нэсэ галя воду)! офигеть! т.е. критерием является "разность" между тем что есть и ответом, который знаем...???? что-то я не втыкнул... что будет является критерием сходимости, когда конечный ожидаемый результат - неизвестен...? например: парименить ГА к задаче дефрагментации - для начала - например дефрагментация диска...
????
15. Crag 10.04.09 14:23
Для этого существует так называемая Фитнес-функция. Которая по заранее определенному алгоритму делает оценку хромосомы. В данном случае - все очевидно, считаем количество совпадений. В более сложных задачах(например в классической задачи про комивояжера) оценивается длина пути и выбирается наименьшая.
Про дефрагментацию, откровенно говоря, не понял.
16. Сhe Burashka (CheBurator) 11.04.09 00:11
да очень просто... имхо, про дефрагментацию: очевидно что в результате дефрагментации диска конечная структура расположения файлов может быть разная. Задача: расположить файлы оптимально, т.е. например находим оптимальное расположение нефрагментированных файлов. вторая задача: найти наикратчайший алгоритм перехода от текущего к оптимальному расположению...
..
как вариант - дефрагментация размещения товара на 3D-складе...
..хотя, возможно, я ахинею несу...
17. Crag 13.04.09 07:21
Здесь сложность будет - каким образом определить является ли это расположение оптимальным. Если это известно, то встанет вопрос с производительностью. Вряд ли на складе лежит три коробки, ведь так?
К примеру мой ГА, написанный на Дельфи решал задачу комивояжера. Если надо было найти путь между, скажем, 100 городами, при большом размере популяции( больше 100) решение задачи занимало не одну минуту. В случае со складом и дефрагментацией - там и хромосомы огромными будут, и математика не малая. Лучше, по-моему, подобные задачи решать тривиально)
18. Иван Иванов (Ivan1874) 27.08.14 03:44
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа