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

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

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

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

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

Сумма максимума и минимума - C++
Добрый день, не могу решить задачку. Задана последовательность целых чисел. Числа нумеруются по порядку следования, начиная с единицы....

Поиск максимума и минимума - C++
Уважаемые форумчане помогите с задачей немогу понять как её зделать. Задание:N точек на площаде заданы своими координатами (xi,yi)....

Вычисление минимума/максимума - C++
Даны действительные числа Х,У,Z.Вычислить 1)max (x+y+z;xyz) 2)min (x+y+z/2;чня)+1

Подсчет минимума и максимума в файле - C++
Помогите решить задачу. &quot;Сформировать файл 1) Фамилия велогонщика 2) Количество минут 3) Количество секунд Петров 20 36 ...

Функции. Поиск минимума и максимума. - C++
Составить программу для нахождения суммы минимального и максимального значений среди элементов каждой из линейных таблиц Х и Y

Поиск минимума и максимума в двумерном массиве - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; int main() { int n; cin &gt;&gt; n; int *a = new int; for...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
FraidZZ
Ex-Member
3898 / 1524 / 229
Регистрация: 06.01.2013
Сообщений: 4,050
Завершенные тесты: 1
09.01.2014, 16:58 #2
Это тебе не в C++ Beginners. Это сразу в C++ для экспертов
0
Tulosba
09.01.2014, 17:04
  #3

Не по теме:

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

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

Цитата Сообщение от MihaniX Посмотреть сообщение
Только не работает нифига... А должно вроде.
вот же
Оно просто ничего не выводит. Не то что не правильно.Вообще не выводит...
0
ilja123
43 / 43 / 7
Регистрация: 24.12.2009
Сообщений: 392
09.01.2014, 20:16 #5
А я ваще не понял, что за генетические скрещивания ? расскажите плзззззззз
0
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);
1
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16697 / 6623 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 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 при компиляции, насчет других не в курсе)
Насчет остального кода не могу сказать, меня убивает однопробельная табуляция..
1
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 минут
пфффф нет по ходу не работает оно....... я уже замучался...........
0
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16697 / 6623 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 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..
1
MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
10.01.2014, 16:04  [ТС] #10
Алгоритм такой:
есть элемент. мы случайным образом его меняем. чем больше значение фитнесса этого элемента (чем он полезнее, лучше) тем выше он стоит в списке (мы его сортируем) и "нижнюю" (худшую) половину заменяем "верхней". Затем случайным образом меняем эти элементы. И так далее несколько кругов. Получается вроде осмысленного перебора.

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

Добавлено через 2 минуты
А сама программа да, вроде работает.
0
S_el
2100 / 1611 / 308
Регистрация: 15.12.2013
Сообщений: 6,451
10.01.2014, 20:07 #11
Цитата Сообщение от MihaniX Посмотреть сообщение
мы случайным образом его меняем
Что значит меняем случайным образом?Случайно выбирается один из операторов?

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

Не по теме:

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

0
MrGluck
Модератор
Эксперт CЭксперт С++
7239 / 4407 / 642
Регистрация: 29.11.2010
Сообщений: 11,927
11.01.2014, 00:40 #13
Цитата Сообщение от KOPOJI Посмотреть сообщение
Кстати, насколько мне известно, объявлять "константы" через #define в плюсах считается "небезопасным", используют const..
нежелательным. Проблема в том, что препроцессорная директива define грубо заменяет одно на другое и информация в отладчике может удивлять и поражать своей "информативностью". В С другого способа нет, в С++ есть константы и предпочтительнее использовать их. Также как inline функции макросам.
0
KOPOJI
11.01.2014, 00:46
  #14

Не по теме:

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

0
MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
11.01.2014, 14:54  [ТС] #15
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение

Не по теме:

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

Не по теме:

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2014, 14:54
Привет! Вот еще темы с ответами:

Функция нахождения минимума и максимума в матрице - C++
Будете добры? Напишите программу .2. Функционал: написать функции нахождения минимума, максимума, наименьшего и наибольшего значения в...

Нахождение максимума и минимума (вставка ассемблера) - C++
Не работает ассемблерная вставка. Как решить проблему? #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;time.h&gt; #include...

Написать функцию определения минимума и максимума - C++
Описать процедуру Minmax(x,y) записывающую в переменную Х минимальное из значений Х и Y, а в переменную Y – максимальное из этих значений...

While(cin>>i) и эффективный алгоритмн нахождения максимума и минимума - C++
В строках &quot;while (cin &gt;&gt; i) { if (i != 666) { money.push_back(i);&quot; не могла остановить считывания, ради эксперимента прописала ...


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

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

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