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

06.04.09

Разработка - Математика и алгоритмы

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

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

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

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

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

 

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

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

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

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

 

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

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


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

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

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

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

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

 

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

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

1 стартмани

09.06.2023    7454    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7852    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8832    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7797    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. CheBurator 3119 06.04.09 12:11 Сейчас в теме
ну, насколько я себе представляю - ГА отличаются быстрой работой в оптимизационных задачах. В чем дает выигрыш данная разработка?
2. detro 46 06.04.09 12:27 Сейчас в теме
Прежде всего это учебная задача, практической пользы нет, мне интересен опыт реализации ГА на 1С. может кто захочет поделиться мыслями, данный вариант моё видение.
Я вижу использование ГА в поиске решений с множеством ограничений. Сейчас не ставил задачу, скорость работы.
3. fedor40 705 06.04.09 14:26 Сейчас в теме
1. Всегда разный результат будет. Клиенту может не понравится.
2. Надо бы сравнить этот метод с методами линейного прог.
4. detro 46 06.04.09 14:37 Сейчас в теме
fedor40 06.04.2009 14:26:25
1) Результат очень сильно зависит от начальной популяции, в чем легко убедиться при работе с текущей обработкой.
Для практического применения просто нужно указывать критерии проходимости, если относительно задачи описанной выше, это может быть % дохода на вложенные средства не меньше чем 20% и пока данный результат не достигнут происходит работа ГА.
Так же для повышения качества результатов необходимо параллельно создавать несколько популяций и среди них выбирать наилучшего.
2) Этого добра много в инете, но как правило задачи в которых параметров большое количество решаются с помощью ГА
5. Anything 89 06.04.09 17:52 Сейчас в теме
Самое сложное в генетических алгоритмах - найти задачу, решение которой требовало бы их использование. ;)
7. detro 46 07.04.09 09:48 Сейчас в теме
(5)
Задачи, которые можно решить с помощью ГА: транспортная логистика – параметры вес, объём машины, вес, объём точки развоза, ограничение по времени работы, как точки так и машины, продолжительность маршрута, стоимость маршрута и т.д.
Если взять задачу описанную выше:
«N заказов поставщику, Х денег — какие заказы необходимо оплатить для получения макс. прибыли за мин. срок времени», добавим сюда важные параметры как дата поступления на склад, планируемые даты отгрузки, ограничение по кол-ву одного вида товаров и т.д., то сразу видно насколько усложняется задача для реализации.
6. fedor40 705 06.04.09 19:42 Сейчас в теме
Задачи:

1) закупка товара по количеству, сумме, весу, объему
2) создание цепочки доставки товара
3) загрузка производственного оборудования
8. Anything 89 07.04.09 13:51 Сейчас в теме
(6) (7) Да, наверное, эти задачи можно решать с помощью ГА.

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

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

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

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

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

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