Форум программистов, компьютерный форум CyberForum.ru

Генетический алгоритм подбора максимума/минимума разных функций - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
09.01.2014, 16:01     Генетический алгоритм подбора максимума/минимума разных функций #1
Собсно, вот:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
 
#define FIRST -50
#define LAST 50
 
using namespace std;
 
const size_t x=10;
 
int fitness(int &n)
{
    n=n*2+n;
    return n;
}
 
void selection(int a[])
{
    for(int i=0; i<x; ++i)
        for(int j=i+1; j<x; ++j)
            if(fitness(a[j])<fitness(a[i]))swap(a[i],a[j]);
    copy(a + x / 2, a + x, a);
}
 
int mutation(int &t)
{
    do
        {
            t += ((rand() % 2 == 1) ? 1 : -1);
        }
        while (FIRST<=t<=LAST);
    return t;
}
 
int main()
{
 
    srand(time(NULL));
 
    int n=0;
    int data_base[x]={n};
 
    /*...*/
 
    for (int rounds=0; rounds<100; rounds++)
    {
        for (size_t i = 0; i < x; ++i)
            data_base[i]=mutation(data_base[i]);
        selection(data_base);
    }
 
    for (size_t i=0; i<x; i++)
        {
            cout<<data_base[i];
        }
    return 0;
}
//Если менять int fitness(int &n) {} можно менять функции. И можно убрать ограничение аргумента #define FIRST -50
#define LAST 50

И искать как минимум, так и максимум (залесть в сортировку и поменять > на <)

Только не работает нифига... А должно вроде.

Идея выросла отсюда:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <numeric>
 
using namespace std;
 
int main()
{
    srand((unsigned int)time(NULL));
    const size_t N = 1000;
    int a[N] = { 0 };
    for (;;)
    {
        for (size_t i = 0; i < N; ++i)
            a[i] += ((rand() % 2 == 1) ? 1 : -1);
        sort(a, a + N);
        copy(a + N / 2, a + N, a);
        cout << accumulate(a, a + N, 0) / N <<endl;
    }
    return 0;
}
Поиск самых больших чисел.

* В планах еще скрещивание осилить))

Добавлено через 2 минуты
Кому интересно, добавил:

Добавлено через 1 минуту


Кому интересно: подбор ключа 2048 бит генетически у меня ~12 секунд подбирает.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
 
using namespace std;
 
#define KEY_LEN 2048 // Длина ключа
bool key[KEY_LEN]; //Неизвестный ключ
 
#define POP_SIZE 20 // Размер популяции
#define ELITE 5 // Количество привелигированных особей
struct gen_struct
{ // Особь, кортеж из генов и значения пригодности
 bool gen[KEY_LEN];
 int fitness;
 gen_struct()
 { //Инициализация случайными значениями
  for(int i=0;i<KEY_LEN;++i)
   gen[i]=(rand()%2==0);
 }
 bool operator<(const gen_struct & g)const
 {
  return (g.fitness>fitness);
 }
 gen_struct(const gen_struct& g)
 {
  for(int i=0;i<KEY_LEN;++i) gen[i]=g.gen[i];
  fitness=g.fitness;
 }
 void Mutate(){ //Оператор мутаций
  gen[rand()%KEY_LEN]=rand()%2;
 }
 void Crossingover(gen_struct & g)
 { //Оператор скрещивания
  for(int i=0;i<KEY_LEN;++i)
    {
   if(rand()%2)
   {
    gen[i]=g.gen[i];
   }
  }
 }
};
 
int Fitness(bool gen[])
{ //Целевая функция
 int ret=0;
 for(int i=0;i<KEY_LEN;i++)
    {
  ret+=(key[i]!=gen[i]);
 }
 return ret;
}
 
 
void GA(gen_struct &ret)
{
 vector<gen_struct> pop;
 pop.resize(POP_SIZE);
 while(1){
  for(int i=0;i<POP_SIZE;++i)
   if((pop[i].fitness=Fitness(pop[i].gen))==0)
     {
      ret=pop[i];
      return;
     }
  sort(pop.begin(), pop.end());
  for(int i=ELITE;i<POP_SIZE;++i)
    {// 5 лучших остаются без изменений
   pop[i].Crossingover(pop[rand()%(ELITE)]);
   pop[i].Mutate();
   for(int i=0;i<KEY_LEN; i++)
   {
     cout << ret.gen[i];
   }
 
  }
 }
}
 
 
int main()
{
    srand(time(NULL));
  cout<<"=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!="<<endl;
  for(int i=0;i<KEY_LEN;i++)
  {
    key[i]=(rand()%2==0);
    cout<<key[i];
  }
  cout<<endl<<"=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!="<<endl;
  gen_struct ret;
  GA(ret);
  cout<<"=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!="<<endl;
  cout << "key=" <<endl;
  for(int i=0;i<KEY_LEN; i++)
  {
    cout << ret.gen[i];
  }
  cout<<endl<<"=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!=!="<<endl;
  cout << endl;
}


Добавлено через 1 минуту
Тоесть 12 секунд если не выводить на экран промежуточную популяцию. Ну вы поняли)

Добавлено через 15 минут
ап...

Добавлено через 20 минут
ни кто не подскажет?...

Добавлено через 12 часов 31 минуту
аппп.......

Добавлено через 4 часа 15 минут
ы...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FraidZZ
Модератор
 Аватар для FraidZZ
3879 / 1505 / 227
Регистрация: 06.01.2013
Сообщений: 4,029
Завершенные тесты: 1
09.01.2014, 16:58     Генетический алгоритм подбора максимума/минимума разных функций #2
Это тебе не в C++ Beginners. Это сразу в C++ для экспертов
Tulosba
09.01.2014, 17:04
  #3

Не по теме:

Цитата Сообщение от MihaniX Посмотреть сообщение
ни кто не подскажет?
единственный вопрос, который я тут увидел.

MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
09.01.2014, 20:11  [ТС]     Генетический алгоритм подбора максимума/минимума разных функций #4
Цитата Сообщение от FraidZZ Посмотреть сообщение
Это тебе не в C++ Beginners. Это сразу в C++ для экспертов
Мог бы создать тему в разделе для экспертов - создал.
Цитата Сообщение от Tulosba Посмотреть сообщение
единственный вопрос, который я тут увидел.
Ну... Я не понимаю почему моя программка не работает. И не понимаю как сделать рабочую.

Цитата Сообщение от MihaniX Посмотреть сообщение
Только не работает нифига... А должно вроде.
вот же
Оно просто ничего не выводит. Не то что не правильно.Вообще не выводит...
ilja123
43 / 43 / 6
Регистрация: 24.12.2009
Сообщений: 382
09.01.2014, 20:16     Генетический алгоритм подбора максимума/минимума разных функций #5
А я ваще не понял, что за генетические скрещивания ? расскажите плзззззззз
Stella
75 / 75 / 5
Регистрация: 26.02.2013
Сообщений: 224
09.01.2014, 20:26     Генетический алгоритм подбора максимума/минимума разных функций #6
MihaniX, вроде тут зацикливание

C++
1
 while (FIRST<=t<=LAST);
распишите как
C++
1
 while (FIRS<=t || t>=  LAST);
KOPOJI
Модератор
 Аватар для KOPOJI
16242 / 6453 / 390
Регистрация: 12.06.2012
Сообщений: 19,353
09.01.2014, 20:29     Генетический алгоритм подбора максимума/минимума разных функций #7

Не по теме:

Цитата Сообщение от MihaniX Посмотреть сообщение
Собсно, вот:
такое чувство, что вы пришли из другого ЯП, и решили "с места в карьер"..


Цитата Сообщение от MihaniX Посмотреть сообщение
Только не работает нифига...
Как именно "не работает" ? Ошибки? Неверно ищет? Еще что-то?
Ошибки, конечно, есть.. К примеру, по мелочам - сравнение знакового int i,j и беззнакового size_t x в цикле, условие FIRST<=t<=LAST.. Как я понимаю (я не особо силен в плюсах), это условие равнозначно "TRUE/FALSE <= LAST" - т.к. одинаковые операции, то выполняется в порядке ассоциативности (гугл сказал, что ассоциативность у него слева направо, как и следовало ожидать). Следовательно, сначала выполнится первое сравнение, в результате получим булево значение, затем полученное булево сравнится с LAST. Т.к. LAST - число, произойдет неявное приведение типов (опять же, не знаю, как в плюсах, но, думаю, что булево приведется к числу, а не наоборот), и получится нечто вроде "1/0 <= LAST". В любом случае, т.к. LAST = 50, условие всегда истинно. Вот вам бесконечный цикл, если, конечно, я нигде не ошибся.. Остальное по аналогии можно посмотреть, включите вывод ошибок (например, если используете g++/gcc - то используйте -Wall при компиляции, насчет других не в курсе)
Насчет остального кода не могу сказать, меня убивает однопробельная табуляция..
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
09.01.2014, 22:30  [ТС]     Генетический алгоритм подбора максимума/минимума разных функций #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
 
#define FIRST -50
#define LAST 50
 
using namespace std;
 
const size_t x=10;
 
int fitness(int &n)
{
n=n;
return n;
}
 
void selection(int a[])
{
for(size_t i=0; i<x; ++i)
for(int j=i+1; j<x; ++j)
if(fitness(a[j])<fitness(a[i]))swap(a[i],a[j]);
copy(a + x / 2, a + x, a);
}
 
int mutation(int &t)
{
do
{
t += ((rand() % 2 == 1) ? 1 : -1);
}
while (FIRST<=t && t<=LAST);
cout<<"|"<<t<<"|";
return t;
}
 
int main()
{
 
srand(time(NULL));
 
int n=0;
int data_base[x]={0};
 
/*...*/
 
for (int rounds=0; rounds<500; rounds++)
{
for (size_t i = 0; i < x; ++i)
data_base[i]=mutation(data_base[i]);
selection(data_base);
}
 
for (size_t i=0; i<x; i++)
{
cout<<data_base[i]<<" ";
}
return 0;
}
Работает верно, но на ограничения не реагирует...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
 
#define FIRST -50
#define LAST 50
 
using namespace std;
 
const size_t x=10;
 
int fitness(int &n)
{
    n=n;
    return n;
}
 
void selection(int a[])
{
    for(size_t i=0; i<x; ++i)
        for(int j=i+1; j<x; ++j)
            if(fitness(a[j])<fitness(a[i]))swap(a[i],a[j]);
    copy(a + x / 2, a + x, a);
}
 
int mutation(int &t)
{
    int x=LAST; int y=FIRST;
    for(;;)
        {
            t += ((rand() % 2 == 1) ? 1 : -1);
            if ((t<=x) && (t>=y)){break;}
        }
    return t;
}
 
int main()
{
 
    srand(time(NULL));
 
    int n=0;
    int data_base[x]={0};
 
    /*...*/
 
    for (int rounds=0; rounds<500; rounds++)
    {
        for (size_t i = 0; i < x; ++i)
            data_base[i]=mutation(data_base[i]);
        selection(data_base);
    }
 
    for (size_t i=0; i<x; i++)
        {
            cout<<data_base[i]<<" ";
        }
    return 0;
}
Вообще ничего не выводит...

Добавлено через 1 час 5 минут
ВОТ! РАБОЧЕЕ! Нашел пару ошибок и исправил.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <cmath>
 
#define FIRST -50
#define LAST 50
 
using namespace std;
 
const size_t x=10;
 
double fitness(double &n)
{
    double x=1/n;
    return x;
}
 
void selection(double a[])
{
    for(size_t i=0; i<x; ++i)
        for(size_t j=i+1; j<x; ++j)
            if(fitness(a[j])<fitness(a[i]))swap(a[i],a[j]);
    copy(a + x / 2, a + x, a);
}
 
double mutation(double &t)
{
    do{t += (( ( (double)(rand() % 2) ) / 100 == 0.01) ? 0.01 : -0.01);}while(t==0 or t<FIRST or t>LAST);
cout<<"|"<<t<<"|";
return t;
}
 
int main()
{
 
    srand(time(NULL));
 
    int n=0;
    double data_base[x]={0};
 
    /*...*/
 
    for (int rounds=0; rounds<500; rounds++)
    {
        for (size_t i = 0; i < x; ++i)
            data_base[i]=mutation(data_base[i]);
        selection(data_base);
    }
    cout<<endl;
    for (size_t i=0; i<x; i++)
        {
            cout<<data_base[i]<<" ";
        }
    return 0;
}
Добавлено через 5 минут
пфффф нет по ходу не работает оно....... я уже замучался...........
KOPOJI
Модератор
 Аватар для KOPOJI
16242 / 6453 / 390
Регистрация: 12.06.2012
Сообщений: 19,353
09.01.2014, 22:38     Генетический алгоритм подбора максимума/минимума разных функций #9

Не по теме:

Цитата Сообщение от MihaniX Посмотреть сообщение
ВОТ! РАБОЧЕЕ!
я все равно так и не понял смысла алгоритма))


З.Ы. объявление переменной n на 43 строчке - лишнее, она не используется, и константы принято обозначать прописными буквами..
З.З.Ы. Не жалейте пробелов, читать же невозможно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdlib>
#include <ctime>
 
#define FIRST -50
#define LAST 50
 
/** by MihaniX **/
 
using namespace std;
 
 
const size_t X = 10;
 
 
double fitness(double &n)
{
    return 1 / n;
}
 
void selection(double a[])
{
    for(size_t i = 0; i < X; ++i)
        for(size_t j = i + 1; j < X; ++j)
            if( fitness(a[j]) < fitness(a[i]) )
                swap(a[i], a[j]);
 
    copy( a + X / 2, a + X, a );
}
 
double mutation(double &t)
{
    do
    {
        t += ( (double) (rand() % 2) ) / 100 == 0.01 ? 0.01 : -0.01;
    }
    while(t == 0);
    
    cout << "|" << t << "|";
    
    return t;
}
 
int main()
{
 
    srand(time(NULL));
 
    double data_base[X] = {0};
 
    /*...*/
 
    for (int rounds = 0; rounds < 500; rounds++)
    {
        for (size_t i = 0; i < X; ++i)
            data_base[i] = mutation(data_base[i]);
        selection(data_base);
    }
    cout << endl;
  
    for (size_t i = 0; i < X; i++)
        cout << data_base[i] << " ";
        
    return 0;
}
Кстати, насколько мне известно, объявлять "константы" через #define в плюсах считается "небезопасным", используют const..
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
10.01.2014, 16:04  [ТС]     Генетический алгоритм подбора максимума/минимума разных функций #10
Алгоритм такой:
есть элемент. мы случайным образом его меняем. чем больше значение фитнесса этого элемента (чем он полезнее, лучше) тем выше он стоит в списке (мы его сортируем) и "нижнюю" (худшую) половину заменяем "верхней". Затем случайным образом меняем эти элементы. И так далее несколько кругов. Получается вроде осмысленного перебора.

Это подготовка к попытке написания программы (python/C++), которая будет генерировать программы (brainfuck).

Добавлено через 2 минуты
А сама программа да, вроде работает.
S_el
1908 / 1503 / 296
Регистрация: 15.12.2013
Сообщений: 5,920
10.01.2014, 20:07     Генетический алгоритм подбора максимума/минимума разных функций #11
Цитата Сообщение от MihaniX Посмотреть сообщение
мы случайным образом его меняем
Что значит меняем случайным образом?Случайно выбирается один из операторов?

Цитата Сообщение от MihaniX Посмотреть сообщение
А сама программа да, вроде работает.
А что нужно?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
10.01.2014, 23:28     Генетический алгоритм подбора максимума/минимума разных функций #12
Цитата Сообщение от FraidZZ Посмотреть сообщение
Это тебе не в C++ Beginners. Это сразу в C++ для экспертов

Не по теме:

Я с ГА разбирался в девятом классе. Никакой магии же там нет.

MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4925 / 2668 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
11.01.2014, 00:40     Генетический алгоритм подбора максимума/минимума разных функций #13
Цитата Сообщение от KOPOJI Посмотреть сообщение
Кстати, насколько мне известно, объявлять "константы" через #define в плюсах считается "небезопасным", используют const..
нежелательным. Проблема в том, что препроцессорная директива define грубо заменяет одно на другое и информация в отладчике может удивлять и поражать своей "информативностью". В С другого способа нет, в С++ есть константы и предпочтительнее использовать их. Также как inline функции макросам.
KOPOJI
11.01.2014, 00:46
  #14

Не по теме:

MrGluck, угу, точно, поэтому все "переменные" в макросе приходится окружать любовью скобками..

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2014, 14:54     Генетический алгоритм подбора максимума/минимума разных функций
Еще ссылки по теме:

C++ Нахождение минимума/максимума в конкретной строке или столбце
Создать функции для обобщенного поиска максимума и минимума в массиве C++
Функция нахождения минимума и максимума в матрице C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
11.01.2014, 14:54  [ТС]     Генетический алгоритм подбора максимума/минимума разных функций #15
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение

Не по теме:

Я с ГА разбирался в девятом классе. Никакой магии же там нет.

Не по теме:

Нету магии! Все просто. Но почему-то в этом разделе народ в основном с радостью отвечает на вопросы типа сортировки массива...

Yandex
Объявления
11.01.2014, 14:54     Генетический алгоритм подбора максимума/минимума разных функций
Ответ Создать тему
Опции темы

Текущее время: 05:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru