Диофантово уравнение

[Мисс Зло]

Помогите пожалуйста....это просто ужас какой то....
Разработать программу для решения Диофантова уравнения вида: a+2b+3c+4d=30, где a,b,c,d - некоторые положительные целые числа. Нахождение коэффициентов a,b,c,d осуществить с помощью генетического алгоритма.

[TinMan]

Сообщение от Мисс Зло

это просто ужас какой то....

А почему ужас-то?
Сама ченть сделала уже? показывай, поможем ))

[BDA]

uses
  crt;

type
  tarray = array[1..4] of integer;
  tmatrix = array[1..20] of tarray;

var
  a: tmatrix;
  i, j: integer;

function f(var a: tarray): integer;
begin
  f := a[1] + 2 * a[2] + 3 * a[3] + 4 * a[4] - 30;
end;

procedure scresh(var a: tmatrix);
var
  i, j, count, j1, j2: integer;
begin
  count := random(20) + 1;
  for i := 1 to count do
  begin
    j1 := random(20) + 1;
    repeat
      j2 := random(20) + 1;
    until j1 <> j2;
    for j := 1 to 4 do
      a[j1, j] := abs((a[j1, j] - a[j2, j]) div 2) + 1;
  end;
end;

procedure mutac(var a: tmatrix);
var
  i, j, count, j1: integer;
begin
  count := random(20) + 1;
  for i := 1 to count do
  begin
    j1 := random(20) + 1;    
    for j := 1 to 4 do
      a[j1, j] := abs(a[j1, j] +  random(10) - 5) + 1;
  end;
end;

procedure selec(var a: tmatrix);
var
  i, j: integer;
  b: tarray;
begin
  for i := 1 to 19 do
    for j := i + 1 to 20 do
      if abs(f(a[i])) > abs(f(a[j])) then
      begin
        b := a[i];
        a[i] := a[j];
        a[j] := b;
      end; 
end;

begin
  randomize;
  for i := 1 to 20 do
    for j := 1 to 4 do
      a[i, j] := random(100) + 1;
  writeln('Search...');
  repeat
    scresh(a);
    mutac(a);
    selec(a); 
    writeln(a[1, 1], ' ', a[1, 2], ' ', a[1, 3], ' ', a[1, 4], ' f=', f(a[1]));
  until abs(f(a[1])) = 0;
  writeln('----------------');
  writeln('Answer: a=', a[1, 1], '; b=', a[1, 2], '; c=', a[1, 3], '; d=', a[1, 4]);
  readln;
end.

Пришлось поломать голову
Да, никаких гарантий 100% работы не даю

[Мисс Зло]

Ой спасибочки)))) вот если бы еще с пояснением, то моей благодарности вообще бы не было предела...)))

[BDA]

Открываем статью на википедии про генетические алгоритмы - http://ru.wikipedia.org/wiki/Генетический_алгоритм.
Смотрим, какие шаги нужно осуществить.

Таким образом, можно выделить следующие этапы генетического алгоритма:
1) Задать целевую функцию (приспособленности) для особей популяции
2) Создать начальную популяцию
(Начало цикла)
1) Размножение (скрещивание)
2) Мутирование
3) Вычислить значение целевой функции для всех особей
4) Формирование нового поколения (селекция)
5) Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

Примерно то же и осуществляем.
Процедура scresh скрещивает случайное количество случайных особей (строк массива).
Процедура mutac изменяет свойства случайного количества случайных особей.
Процедура selec сортирует всех особей-строк по возрастанию расстояния до требуемого значения.
На первой строке массива будет самая приспособленная особь.

[Мисс Зло]

а почему мы всегда берем 20 особей? или это не имеет значения?

[BDA]

Генетический алгоритм такая вещь, что с параметрами можно "играться" бесконечно. Мне приглянулось число 20
Любой шаг можно сделать многими путями (это я про способы скрещивания и мутирования).

это не имеет значения?

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

[TinMan]

Сообщение от BDA

Пришлось поломать голову

BDA, респект! ))
+1

[Мисс Зло]

а еще вопросы))) a[j1, j] := abs((a[j1, j] - a[j2, j]) div 2) + 1 вот эта формула откуда...? и последующие в процедурах)))

[BDA]

Так я говорю, что это широкий простор для творчества)
Формулы взяты "от балды".
a[j1, j] := abs((a[j1, j] - a[j2, j]) div 2) + 1; - заменяет 1 особь на гибрид из 1 и 2 особи
Главное - чтобы числа оставались в области определения, т.е. целые положительные.
a[j1, j] := abs(a[j1, j] + random(10) - 5) + 1; - особь 1 мутирует случайным образом.