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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
#1

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

09.01.2014, 16:01. Просмотров 2561. Ответов 14
Метки нет (Все метки)

Собсно, вот:
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 минут
ы...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2014, 16:01     Генетический алгоритм подбора максимума/минимума разных функций
Посмотрите здесь:

C++ Функции. Поиск минимума и максимума.
C++ Поиск максимума и минимума
Вычисление минимума/максимума C++
C++ Массив: Определить сумму максимума и минимума последовательности.
Функция нахождения минимума и максимума в матрице C++
C++ Сумма максимума и минимума
C++ Написать функцию определения минимума и максимума
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FraidZZ
Ex-Member
3897 / 1523 / 229
Регистрация: 06.01.2013
Сообщений: 4,049
Завершенные тесты: 1
09.01.2014, 16:58     Генетический алгоритм подбора максимума/минимума разных функций #2
Это тебе не в C++ Beginners. Это сразу в C++ для экспертов
Tulosba
09.01.2014, 17:04
  #3

Не по теме:

Цитата Сообщение от 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 / 7
Регистрация: 24.12.2009
Сообщений: 392
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
Модератор
Эксперт HTML/CSSЭксперт PHP
16680 / 6606 / 427
Регистрация: 12.06.2012
Сообщений: 19,840
Завершенные тесты: 1
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
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
Модератор
Эксперт HTML/CSSЭксперт PHP
16680 / 6606 / 427
Регистрация: 12.06.2012
Сообщений: 19,840
Завершенные тесты: 1
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
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
10.01.2014, 16:04  [ТС]     Генетический алгоритм подбора максимума/минимума разных функций #10
Алгоритм такой:
есть элемент. мы случайным образом его меняем. чем больше значение фитнесса этого элемента (чем он полезнее, лучше) тем выше он стоит в списке (мы его сортируем) и "нижнюю" (худшую) половину заменяем "верхней". Затем случайным образом меняем эти элементы. И так далее несколько кругов. Получается вроде осмысленного перебора.

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

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

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

Не по теме:

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

MrGluck
Ворчун
Эксперт CЭксперт С++
6676 / 3857 / 511
Регистрация: 29.11.2010
Сообщений: 10,217
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++ While(cin>>i) и эффективный алгоритмн нахождения максимума и минимума
Найти сумму максимума и минимума заданных последовательностей C++
Поиск минимума и максимума в двумерном массиве C++
C++ Поиск минимума и максимума в динамическом массиве указателей

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

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

Не по теме:

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

Не по теме:

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru