Генетический алгоритм, Применение и реализация Опции

[LOVE133]

Задача : Имеется инвестиционный капитал , который нужно распределить среди 10 фирм.Для каждой фирмы задана функция зависимости прибыли от объема вложений.Требуется найти наиболее прибыльный вариант распределения капитала при условии, что заданы минимальный и максимальный объемы вложения для каждого проекта.
Решать собираюсь так - Распределяем рандомом капитал,задаем для каждого предприятия функцию,максимальное и минимальное вложение.Теперь вопросы
1) что брать за хромосому?
2) как определить оценочную функцию в данном случае?Стремиться все должно к максимуму прибыли, но какой функцией это реализовывать?
3) Как определить функицю мутации и коэффициент мутации.
В задаче должны варьироваться количество хромосом N ( я так думаю - это количество возможных вариантов из которых делается селекция и мутации) , и этот самый коэффициент мутации.

[Lapp]

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

> 1) что брать за хромосому?
Вектор капиталовложений. Иначе говоря, массив из десяти значений, каждое из которых означает, сколько вложено в эту фирму. Понятно, что свертка этого вектора равна полной сумме расходов.

> 2) как определить оценочную функцию в данном случае?
> Стремиться все должно к максимуму прибыли, но какой
> функцией это реализовывать?
Как я понимаю, тебе даны функции нормы прибыли (то есть прибыль на вложенную денежную единицу). Полная прибыль к фирмы есть произведение этой функции (взятой от реального значения вложенного капитала) на вложенный капитал. Сумма таких произведений по всем фирмам и есть полная прибыль. Ее и надо максимизировать.

> 3) Как определить функицю мутации и коэффициент мутации.
Хм, это надо подумать.. Например, можно в векторе один параметр менять случайным образом. При этом все остальные подгонять под это изменение так, чтоб сумма оставалась прежней. Коэффициент будет определять среднюю величину мутации.

> В задаче должны варьироваться количество хромосом N
> ( я так думаю - это количество возможных вариантов из которых
> делается селекция и мутации) , и этот самый коэффициент мутации.
А почему у тебя нету размножения? Мне кажется, именно оно должно главенствовать в процессе..

[LOVE133]

Давайте вместе...Делаем так
1) 1 хромосома - одна инвестиция в i-ое предприятие
2) особью будет считаться тот самый вектор , который состоит из 10 хромосом инвестиций в каждое предприятие .Вот тут вопрос сразу, как инициализировать особь ( создать 10 хромосом ) в зависимости от того что нам заданы макс. и мин. вложений? Это уже больше к Паскалю, чем к алгоритму...Так же вопрос о количестве хромосом отпадает, я понимаю их ровно 10 и не больше, ни меньше. Генотип особи - есть решение
3) создаем популяцию - какое-то количество особей.Выживаемость каждой особи будет являться значение той самой оценочной функции (Fitness ), то есть считаем прибыль в каждом случае и ставим это за коэффициент выживаемости. Только как сформировать функцию, елси нам даны только ( да и то в условии не даны, сама придумаю ) значения функция для каждой отдельной фирмы?
4) начинаем цикл эволюции "Он подразделяется на три основные операции: подсчет вероятностей стать родителем для особей популяции (селекция или отбор), порождение новой популяции (скрещивание и мутация), и пересчет коэффициентов выживаемости особей с проверкой условия выхода из цикла (которым является либо удельный коэффициент выживаемости – т.е. найдена особь точно соответствующая решению задачи, либо достижение порогового значения числа итераций цикла эволюции)" ( цитирую книжки)
5) ранжировать популяцию по возможности стать родителем _ то есть у кого выше fitness . того и будем скрещивать , отбираем, скрещиваем - из 2 родителей получается 2 потомка с обменявшимися генокодами? проверяем для всех новых особей fitness и заменяем половину плохих особей на половину лучших получившихся новых
6) Дальше выполняем мутацию , смотрим результат.

осоновная проблема - это определить fitness , так как функция оценки не дана ;)

[Lapp]

Видимо, с хромосомами я ошибся: я думал, что это примерно то же самое, что и особь. Ладно, пусть у тебя хромосома - это то, что я считал одним геном.
Но почему ты считаешь, что оценочная функция не дана?

осоновная проблема - это определить fitness , так как функция оценки не дана ;)

На мой взгляд, это и есть прибыль! Выражусь более конкретно.
Пусть Si - это вложение капитала в i-ю фирму (то есть то, что ты считаешь хромосомой, а я - гЕном.
Пусть Fi(S) - это норма прибыли i-й фирмы как функция от вложения.
Тогда Si*Fi(Si) - это и есть прибыль с i-й фирмы.
Полная прибыль со всех фирм составит
i=10
<Сигма> Si*Fi(Si)
i=1
Это и есть твой фитнесс, или здоровье, или что там еще хочешь, а короче - полная прибыль. Разве не так?..
Если тебе не даны сами функции Fi - это другой вопрос. Ну, придумай.. Единственное, что могу сказать - они должны иметь максимум в обозримой области, то есть фирму можно пересытить вложениями так, что она не сможет их освоить надлежащим образом.

[LOVE133]

Я села на том, что никак не могу считать из файла матрицу... Как я вообще доучилась до 3 курса...

Код

Program genalgoritm;
  uses crt;
  Type
    TMatrix = array [1..10,1..10] of integer;

    THromosome = record
     Code :array [1..100] of integer;
     Eval: integer;
    end;

    TGeneration= array [1..10 ] of Thromosome;

  var
  i,j,n :integer;
  Mat :Tmatrix;
  f:file of integer;
  begin
  clrscr;
  assign (f,'matrix.txt');
  reset ( f );
     for i:=1 to 10 do
      for j:= 1 to 10 do
      begin
      read (f,mat[i,j]);
      write(mat[i,j]);
      readln;
      end;
  close (f);
   for i:=1 to 10 do
     for j:=1 to 10 do
     begin
      write ( mat[i,j]); writeln;
     end;
     readln;
  end.

Файл matrix.txt набивается числами типа
100 200 300 400 500
12 12 12 23 43
12 12 12 23 43
12 12 12 23 43
12 12 12 23 43
где верхняя строка - величина вклада, столбцы - это прибыль если столько вложить в предприятие...

Сообщение отредактировано: LOVE133 - 13.11.2007 20:00

[Lapp]

Я села на том, что никак не могу считать из файла матрицу
...
Файл matrix.txt набивается числами типа
100 200 300 400 500
12 12 12 23 43
12 12 12 23 43
12 12 12 23 43
12 12 12 23 43
где верхняя строка - величина вклада, столбцы - это прибыль если столько вложить в предприятие...

Судя по расширению (.txt) и по виду, а также по тому, что он "набивается", я подозреваю, что у тебя данные в текстовом файле, а не в типизированном. Зачем же ты его описываешь как file of integer? Опиши так:
f:text;
И дальше используй операторы Read и ReadLn аналогично вводу с клавиатуры.
И еще: если есть ошибка, говори какая она. Догадываться уже надоедает..

[LOVE133]

Домучали...Если кому понадобится, в файле готовый вариант решения с применением ген.алгоритма