Решение задачи распределения капиталовложений

Инициализация хромосом

1. i:=1;
2. while i<=pop_size do                          //пока не достигнут размер популяции
3.      stat_model(x,Pr);                            //статистическое моделирование
4.      hr[i]:=x;           //присвоение хромосоме удачный результат
5.      inc(i);

     Процесс кроссинговера

1. j:=0;
2. for i:=1 to pop_size do              //цикл для выбора родительских хромосом
3.      r:=random;
4.      if r<=Pc then                         //Pc – коэфициент модификации
5.          inc(j);
6.          parent[j]:=hr[i];                //родитель найден
7.         pos[j]:=i;                           //позиция родителя в популяции
8. if j-нечетное then j:=j-1;
9. i:=1;
10. While i<j do                            //цикл кроссинговера
11.      c:=random;
12.        for k:=1 to n do
13.             hr[pos[i],k]:=round(c*parent[i,k]+(1-c)*parent[i+1,k]);             //модификация
14.             hr[pos[i+1],k]:=round((1-c)*parent[i,k]+c*parent[i+1,k]);        //модификация
15.        i:=i+2;

Процесс мутации

1. j:=0;
2. for i:=1 to pop_size do                   //цикл выбора родительских хромосом
3.      r:=random;
4.      if r<=Pm then                             //Pm – коэффициент модификации
5.           inc(j);
6.           parent[j]:=hr[i];                    //родитель найден
7.           pos[j]:=i;                               //номер родителя в популйции
8. i:=1;
9. l:=0;                                               //счетчик для выхода при плохом направлении
10. While i<=j do                                //цикл мутации
11.   inc(l);
12.   for k:=1 to n do
13.        c[k]:=random*power(-1,random);    //формирование случайного направления       
14.   M:=random;                                            //количество шагов в направлении
15.   for k:=1 to n do parent[i,k]:=round(parent[i,k]+M*c[k]);  //модификация
16.   if odz(parent[i]) then                   //если новая хромосома удовлетворяет одз
17.        hr[pos[i]]:=parent[i];             //она заменяет родителя
18.        inc(i);                       
19.       l:=0;
20.   Else                                            //если же нет, то
21.      M:=random(M);                   // новое количество шагов <M
22.        if l>=10 then inc(i);              //проверка счетчика на выход

Селекция  хромосом

До этого  нами уже была проведена сортировка хромосом и вычислена для каждой функция приспособленности (Eval):

1. for i:=1 to pop_size do                           //цикл по всей популяции
2.   q[i]:=0;
3.      for j:=1 to i do q[i]:=q[i]+Eval[j]; //вычисление кумулятивной вероятности
4. for j:=1 to pop_size do              //новый цикл для определения новой популяции
5.      r:=random*q[pop_size];     //определение номера хромосомы
6.    i:=1;
7.      while q[i]<=r do inc(i);
8.            hr1[j]:=hr[i];                 //переход одной хромосомы в новую популяцию

Пример  реализации

В качестве примера  было взято n=5 (количество станков), общая стоимость α=12500, размер склада b=500, вектор стоимости станков (300,800,700,900,1000), вектор площади станков (20,30,50,30,10). Вектор желаемого исхода (0.97, 0.95,  0.90). Количество циклов статистического моделирования равен 3000, генетического алгоритма - 400

Результат работы программы выглядит следующим образом:

X=(7,4,2,3,2) , общая стоимость = 11400, общая площадь = 470, вектор исходов (0.99, 0.95, 0,89) 
 
 
 

Литература

1. Б. Лю. Теория и практика неопределенного программирования. -  М.: Бином: Лаборатория знаний, 2005.
2. Iwamura, K and Liu, B., Dependet-chance integer programming applied to capital budgeting, Journal of the Operations Research Society of  Japan, Vol.42, No. 2, 117-127, 1999.
3. Ермольев Ю.М. Методы стохастического программирования. – М.: Наука, 1976.
4. Юдин Д.Б. Задачи и методы стохастического программирования. – М.: Сов. радио, 1979.
5. Вентцель Е.С. Исследование операций. – М.: Сов. радио 1972.
6. Горбань А.Н. Обучение нейронных сетей. – М.: СП ПараГраф, 1990.
7. http://orsc.edu.cn/~liu

 
 
 
 
 
 
 
 
 
 
 

Приложение

program Gibrid;

uses

  SysUtils,Math;

const max=10;

const Nmax=3000;

const pop_size=10;

const mu1=1;

const bt=4/3;

const ap=0.05;

const nu1=0.01;

Type koef=array [1..max] of real;

Type ves=array[1..max] of koef;

Type mis=array[1..Nmax] of real;

Type learn=array[1..Nmax,1..max] of real;

Type hromo=array[1..pop_size] of koef;

Type position=array[1..max]of integer; 

var     mu:real;

  cost,sq:position;

 d,ogr,dd,x:koef;

w0,w1,zn:ves;

 max_st_m,gen_alg:integer; 

function LogN(mu, sigma: real):real;

var u1,u2,y: real;

begin

randomize;

u1:=random;

u2:=random;

y:=sqrt(-2*ln(u1))*sin(2*Pi*u2);

y:=mu+sigma*y;

result:=exp(y);

end; 

function Expa(sigma:real):real;

var u:real;

begin

randomize;

u:=random;

result:=-sigma*ln(u);

end; 

procedure uslovie;

var i:integer;

begin

writeln('Input cost: ');

for i:=1 to 5 do

  begin

  write(i,' = ');

  readln(cost[i]);

  end;

write('Input max cost: ');

readln(ogr[1]);

writeln('Input square: ');

for i:=1 to 5 do

  begin

  write(i,' = ');

  readln(sq[i]);

  end;

write('Input max sq: ');

readln(ogr[2]);

writeln('Input fun result (0,1): ');

for i:=1 to 3 do

  begin

  write(i,' = ');

  readln(d[i]);

  end;

writeln;

for i:=1 to 5 do

  if i<5 then write(cost[i],'*x[',i,']+')

    else write(cost[i],'*x[',i,']= ');

writeln(ogr[1]);

writeln;

for i:=1 to 5 do

  if i<5 then write(sq[i],'*x[',i,']+')

    else write(sq[i],'*x[',i,']= ');

writeln(ogr[2]);

write('Input max iter of stat.model (0..3000) = ');

readln(max_st_m);

write('Input num of gen algoritm = ');

readln(gen_alg);

end; 

function odz(x:koef):boolean;

var

     j:integer;

summ1,summ2:real;

begin

summ1:=0;

for j:=1 to 5 do

  summ1:=summ1+cost[j]*x[j];

summ2:=0;

for j:=1 to 5 do

  summ2:=summ2+sq[j]*x[j];

if (summ1<=ogr[1]) and (summ2<=ogr[2]) and (x[1]>=0) and (x[2]>=0) and (x[3]>=0) and (x[4]>=0) and (x[5]>=0) then

result:=true

                                   else result:=false; 

end; 

procedure stat_model(var x:koef; var dd:koef);

var

     i,N1,k:integer;

begin

repeat

for i:=1 to 5 do

  begin

  randomize;

  x[i]:=round(random*10);

  end;

if odz(x) then

  begin

  N1:=0;

  for k:=1 to max_st_m do

    if LogN(3,1)*x[1]>=Expa(10) then N1:=N1+1;

  dd[1]:=N1/max_st_m;

  N1:=0;

  for k:=1 to max_st_m do

    if LogN(4,1.6)*x[2]>=Expa(15) then N1:=N1+1;

  dd[2]:=N1/max_st_m;

  N1:=0;

  for k:=1 to max_st_m do

    if (LogN(5,1.6)*x[3]>=Expa(20)) and (LogN(4,1.2)*x[4]>=Expa(18)) and (LogN(3,0.8)*x[5]>=Expa(16)) then N1:=N1+1;

  dd[3]:=N1/max_st_m;

  end;

until odz(x);

end; 

procedure pech(hr:hromo);

var i,j:integer;

begin

for i:=1 to pop_size do

  begin

  for j:=1 to 5 do

  write(hr[i,j]:4:2,'  ');

  writeln

  end;

end; 

procedure stat_res(x:koef; var dd:koef);

var

     N1,k:integer;

begin

N1:=0;

for k:=1 to max_st_m do

  if LogN(3,1)*x[1]>=Expa(10) then N1:=N1+1;

dd[1]:=N1/max_st_m;

N1:=0;

for k:=1 to max_st_m do

  if LogN(4,1.6)*x[2]>=Expa(15) then N1:=N1+1;

dd[2]:=N1/max_st_m;

N1:=0;

for k:=1 to max_st_m do

  if (LogN(5,1.6)*x[3]>=Expa(20)) and (LogN(4,1.2)*x[4]>=Expa(18)) and (LogN(3,0.8)*x[5]>=Expa(16)) then N1:=N1+1;

dd[3]:=N1/max_st_m;

end; 

procedure init(var hr:hromo);

var i,j:integer;

    dd:koef;

begin

i:=1;

while i<=pop_size do

  begin

  stat_model(x,dd);

  for j:=1 to 5 do hr[i,j]:=x[j];

  inc(i);

  end;

end; 

procedure cross(var hr:hromo);

var i,j,k:integer;

    r,c:real;

    parent:hromo;

    pos:position;

begin

j:=0;

for i:=1 to pop_size do

  begin

  randomize;

  r:=random;

  if r<=0.3 then

    begin

    inc(j);

    parent[j]:=hr[i];

    pos[j]:=i;

    end;

  end;

if ((j mod 2)=1)then j:=j-1;

i:=1;

While i<j do

  begin

  randomize;

  c:=random;

  for k:=1 to 5 do

  begin

  hr[pos[i],k]:=round(c*parent[i,k]+(1-c)*parent[i+1,k]);

  hr[pos[i+1],k]:=round((1-c)*parent[i,k]+c*parent[i+1,k]);

  end;

  i:=i+2;

  end;

end; 

procedure mut(var hr:hromo);

var i,j,k,l,M:integer;

    r:real;

    parent:hromo;

    pos:position;

    c:koef;

begin

j:=0;

for i:=1 to pop_size do

  begin

  randomize;

  r:=random;

  if r<=0.2 then

    begin

    inc(j);

    parent[j]:=hr[i];

    pos[j]:=i;