Поиск минимума функции
Msg : 1423 из 4511 -1389 From : Yuri Burger 2:468/85.3 Птн 09 Июн 00 19:09 To : Andrew Filinsky Вск 11 Июн 00 09:04 Subj : Поиск минимума функции
Всего тебе и привет Andrew! 09 Jun 00 02:53, Andrew Filinsky wrote to All: AF> Hайти минимум дискретной функции в дискретном N-мерном пространстве (N = AF> 43). Аргументы функции могут принимать целые значения от 0 до 255, а AF> функция может принимать целые значения в диапазоне от 0 до 2^30. [укусил] AF> Есть стандартные методы / ваши предложения и идеи? Если есть какие стандартные способы - решай ими. Если не найдешь, то пробый ген. алгоритм - в любом случае затраты малы, прогу для него можно за час сделать, а то и быстрее :) Вот, что я решал им для курсака: найти максимум функции: z=fabs(127+200*(cos(sx*sx+sy*sy)*cos(sy*sx))*sqrt(sin(sx)*sin(sy)) sx=x*PI/MaxX sy=y*PI/MaxY x,y принимают значения на интервале 0 - 1024 с кодировкой в 32 бита, тобишь тут 10 бит на число до запятой, остальное на число после запятой. Hа рисунке эта вункция имеет как минимум 8 вершин - ярко выраженных. Параметры для ген. алгор. : размер окна для селекции - 16 макс. длина популяции - 128 процент мутаций среди особей - 8% процент мутаций среди ген - 8% При рассмотрении 16,392 вариантов решений, уже имелось вот что: для X=814.275 и Y=812.501 Z принимает значение 246.482 Hа этом я прервал поиск (который длился около 3-5 секунд). Для сравнение: неполный перебор (с шагом 4) по пространству XY дал решение для X=816 и Y=812 Z принимает значение 246.467 ЗЫ: как на мой взгляд, то вполне целесообразно пустить ген. алгоритм, подождать около 5 минут, если решение не улучшается, то брать его... ЗЫЗЫ: Помоему твоя задача схожа с этой. За сим прощаюсь, K. --- * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
Msg : 1499 из 4511 -1447 From : Yuri Burger 2:468/85.3 Срд 14 Июн 00 20:26 To : Alexander Tsyplakov Суб 17 Июн 00 00:32 Subj : Поиск минимума функции
Всего тебе и привет Alexander! 12 Jun 00 08:05, Alexander Tsyplakov wrote to All: >> Если есть какие стандартные способы - решай ими. Если >> Вот, что я решал им для курсака: >> найти максимум функции: >> AT> z=fabs(127+200*(cos(sx*sx+sy*sy)*cos(sy*sx))*sqrt(sin(sx)*si AT> n(sy)) AT> Юрий, а Вы не могли бы дать ссылки в Интернете по AT> оптимизации с помощью ген. алгоритмов или объяснить более AT> подробно алгоритм для максимизации такого рода функций? К сожалению ссылок не имею, да и описаний алгоритма у меня никаких нет - всё делалось почти что из одного названия :) Вот что я знаю: 1. Имеем набор Xi (i=1,m) для функции вида F(X1,...,Xm). 2. Известен интервал, на котором лежат Xi. Самый простой вариант, когда этот интервал равен 0..XMax 3. Hеобходимо осуществить проекцию каждого Xi на бинарный вектор. Интерисует восновном получение Xi из этого вектора: q X=( E (B[j] * 2^j))*XMax/((2^q)-1) j=0 Сдесь q - длина бинарного вектора для каждого X B[j] - значение j-го бита (0 или 1) Тобишь этотот вектор - ничто иное, как число с фиксированной запятой, представленное в двоичном коде. 4. Теперь расширяем этот вектор так, чтоб в нём вместились все Xi. Теперь его длина составит m*q. Соответственно реализуем извлечение каждого Xi из этого вектора (ну это вроде просто :) 5. Теперь делаем массив, где будет лежать вся популяция таких векторов (особи). Каждой особи присвоим значение нашей оценочной функции F 6. Реализуем функцию мутации - с заданой вероянтостью выбераются особи и соответственно номера генов (бит) в них. Выбранные гены в выбранных особях инвертируются. 7. Реализуем функцию скрещивания (кроссинговер): случайно выбераем точку на интервале 0..q и генерим из двух особей еще две по правилу: потомок1= часть до выбранной точки от предка 1, часть после от предка 2 потомок2= часть до выбранной точки от предка 2, часть после от предка 1 Теперь, собственно алгоритм: 1 заполняем популяцию особями со случайно подобранными векторами 2 сортируем популяцию 3 берем первые <несколько> особей скрещиваем из "все на все" каждый полученный мутируем с заданной вероятностью добавляем его в популяцию (если его оценка хуже всех имеющихся в популяции, то убиваем его. Иначе выбираем особь из популяции вместо которой посадим эту) 4 переход на 3 Вот по такому принципу я сделал прогу. Щас переделал её так, чтоб можно было вводдить любые функции - у меня потребовали, чтоб она решала симплекс-задачи. Вот последний результат: максимизировать Z=9*x1 + 10*x2 + 16*x3 ограничения: 16*x1 + 15*x2 + x3 <= 360 6*x1 + 4*x2 + 4*x3 <= 192 3*x1 + 3*x2 + 4*x3 <= 180 пространство возможных планов сдесь в районе 1000^3 Целочисленный симплекс даёт решение Z=720 ГА перебрал около 380 тысяч решений и нашел Z=719.021 для x1=0.304442 x2=0.0312378 x3=44.748 Думал он при этом гдето около 5и минут За сим прощаюсь, K. --- * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)