|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:468/85.3 03 Feb 2002 16:51:02
To : Artyom Petrov
Subject : Вопрос по ГА
--------------------------------------------------------------------------------
29 Jan 02 23:41, Artyom Petrov wrote to All:
AP> Где я не читал про ГА, такое ощущение что везде предполагается, что длина
AP> битового представления реальных значений у всех варьируемых
AP> параметров одинакова.
Почему? Hе обязательно.. просто при исследовании эффективности ГА обычно
пользуются тестовыми функциями n переменных, т.к. для теста нужна достаточно
сложная функция лучшие решения которой уже известны - сочинять самому
геморойно, а существующие - это в основном функции переменных с одинаковым
пространством значений.
AP> Hо это чаще всего не так.
Это уж как попадется.. Мне приходилось решать всего 3-4 задачи: поиск
максимума функции (все переменные одного размера), поиск оптимальной молекулы
(комбинаторика - 4 радикала, каждый принимает значение из одного алфавита),
поиск формы функции, заданной таблично... Знакомые сталкивались с поиском
оптимальной смеси кормов, поиском оптимальной очереди обслуживания кораблей в
порту, оптимальной раскройкой листа.. В этих задачах все параметры одинаковой
длины.
И потом, самые популярные задачи для ГА из комбинаторики (плагодаря NP), а
там опять-же все параметры одной длины.
AP> У меня есть реальная задача идентификации функции.
Подробней можно? Тебе апроксимировать нужно? Какие есть наработки? (просто
я уже с пол года над такой задачей сижу, и еще по меньшей мере пол года буду
сидеть :)
AP> Есть двенадцать параметров, из них четыре требуют 16-20 бит, а есть
AP> четыре которым достаточно 2-3. Мне кажется что 3-ох битовые параметры
AP> будут значительно реже менятся, по сравнению с 20-и битовыми (я имею
Хм.. Если посмотреть на это с точки зрения вклада каждого параметра в
размер пространства возможных решений... каждый параметр определяет ось в
n-мерном пространстве заданной длины (число значений параметра).. тогда чаще
исследовать нужно оси большей длины, т.к. там пространство больше.. значит
кодирование параметров разным числом бит вполне справедливо.
AP> не унифицированный кроссинговер), то есть они конечно должны реже
AP> менятся, но это будет не совсем пропорционально.
Почему? Можно по другому подойти.. Отбросим оси.. Рассматриваем каждое
решение в виде единственного "параметра", вмещающего реальные параметры.
Определяем предельное число бит каждому реальному параметру, в соответствии с
числом принимаемых им значений. Ложим все кодированные параметры в бит-вектор
(тот единственный "параметр"). Этот вектор накрывает собой все возможные
решения (если повезет, то еще и не захватывает невозможные :) Тогда,
пространство перебора - возможные значения этого вектора. Всё. Дальше реализуем
перебор. Вопрос о частоте изменений отдельных параметров вообще не стоит - мы
работатем с одним самодостаточным вектором...
AP> Вопрос: как с этим бороться?
Вообще, вся прелесть ГА в том, что плотность/частота изменений отдельных
участков хромосомы настраивается косвенно в процессе работы алгоритма. Об этом
и говорится в теореме о шеммах - если постоянные значения некоторого участка
хромосомы приводят к лучшим значения, то пример такой хромосомы больше
распространится по популяции.. как следствие - вероятность того что у обоих
родителей этот участок будет одинаков повысится, а значит у чилдрена он тоже
будет таким-же (если не мутирует). Тоесть как бы автоматически произойдет
уплотнение и растяжение хромосомы в нужных местах.
Kрюгер.
---
* Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Вопрос по ГА 
