SI2020/gmo.cpp

300 lines
5.9 KiB
C++

#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>
#include <math.h>
#include<bits/stdc++.h>
#include <algorithm>
#include <utility>
using namespace std;
string generateValue() {
char trash[100];
string x = itoa(rand() % 1000,trash,10);
if (x.size() == 2) {
x = "0" + x;
}
else if (x.size() == 1) {
x = "00" + x;
}
return x;
}
string generateVegetable() {
string taste = generateValue();
string colour = generateValue();
string size = generateValue();
return taste + colour + size;
}
void generatePopulation(string * population,int length) {
int i;
for(i=0;i<length;i++) {
population[i] = generateVegetable();
}
}
int power(int x, int y) {
if (y == 0) return 1;
if (y == 1) return x;
int temp = power(x, y/2);
if (y%2 == 0) return temp * temp;
else return x * temp * temp;
}
int stringToInt(string str,int size) {
int x = 0;
int i;
reverse(str.begin(),str.end());
for(i=0;i<size;i++) {
x += (str[i] - '0') * power(10,i);
}
reverse(str.begin(),str.end());
return x;
}
int fitness(string vegetable) {
int taste = stringToInt(vegetable.substr(0,3),3);
int colour = stringToInt(vegetable.substr(3,3),3);
int size = stringToInt(vegetable.substr(6,3),3);
return (taste+colour+size)/3;
}
bool comparePair(const pair<int, string>&i, const pair<int, string>&j)
{
return i.first > j.first;
}
void ranking(string * population,string * parents, int populationSize, int parentsNumber) {
int i;
pair <int,string> fitnessTable[populationSize];
for(i=0;i<populationSize;i++) {
fitnessTable[i] = make_pair(fitness(population[i]),population[i]);
}
sort(fitnessTable,fitnessTable+populationSize,comparePair);
for(i=0;i<parentsNumber;i++) {
parents[i] = fitnessTable[i].second;
}
}
bool exists(int len, int * array, int element) {
int i;
for(i=0;i<len;i++) {
if (array[i] == element) return true;
}
return false;
}
void selection(string * population,string * parents, int populationSize, int parentsNumber) {
int i,j,k;
pair <int,string> fitnessTable[populationSize];
for(i=0;i<populationSize;i++) {
fitnessTable[i] = make_pair(fitness(population[i]),population[i]);
}
sort(fitnessTable,fitnessTable+populationSize,comparePair);
int roulette;
int taken[parentsNumber];
int sum = 0;
for(i=0;i<parentsNumber;i++) {
for(j = populationSize - 1;j>=0;j--) {
if(not exists(parentsNumber,taken,j)) {
sum += fitnessTable[j].first;
fitnessTable[j].first = sum;
}
}
roulette = rand() % fitnessTable[0].first;
j = 0;
while(exists(parentsNumber,taken,j)) {
j += 1;
}
while(roulette > fitnessTable[j].first and j<populationSize) {
if(not exists(parentsNumber,taken,j)) {
roulette -= fitnessTable[j].first;
}
j+=1;
}
parents[i] = fitnessTable[j].second;
taken[i] = j;
}
}
int newton(int n,int k) {
if (k==0 or n==k) return 1;
else return newton(n-1,k-1) + newton(n-1,k);
}
string mutate(string child) {
int d3 = rand() % 3;
string mutation = generateValue();
switch(d3) {
case 0:
child = mutation + child.substr(3,6);
break;
case 1:
child = child.substr(0,3) + mutation + child.substr(6,3);
break;
case 2:
child = child.substr(0,6) + mutation;
break;
}
return child;
}
string cross(string parent[2]) {
int i;
string child = "";
for(i=0;i<3;i++) {
child += parent[rand() % 2].substr(i*3,3);
}
if (child == parent[0] or child == parent[1]) {
string other;
if (child == parent[0]) other = parent[1];
else other = parent[0];
int d3 = rand() % 3;
switch(d3) {
case 0:
child = other.substr((rand() % 3)*3,3) + child.substr(3,6);
break;
case 1:
child = child.substr(0,3) + other.substr((rand() % 3)*3,3) + child.substr(6,3);
break;
case 2:
child = child.substr(0,6) + other.substr((rand() % 3)*3,3);
break;
}
}
int d1000 = rand() % 1000;
if (rand() % 100 == 0) {
child = mutate(child);
}
return child;
}
void crossover(string * parents,string * nextGen,int parentsNumber,int nextGenSize) {
int counter = 0;
int i,j;
for(i=0;i<parentsNumber;i++) {
if (counter >= nextGenSize) {
break;
}
else {
nextGen[counter] = parents[i];
counter +=1;
}
}
while(counter < nextGenSize) {
for(i=0;i<parentsNumber;i++) {
if (counter >= nextGenSize) {
break;
}
else {
for(j=i;j<parentsNumber;j++) {
if (counter >= nextGenSize) {
break;
}
else {
string couple[2];
couple[0] = parents[i];
couple[1] = parents[j];
nextGen[counter] = cross(couple);
counter += 1;
}
}
}
}
}
}
void genetic_algorithm(string * population, int populationSize, int parentsNumber,string * outcome, int outcomeSize) {
int iteration,i;
for(iteration=0;iteration<5;iteration++) {
string * parents = new string[parentsNumber];
selection(population,parents,populationSize,parentsNumber);
string * nextGen = new string[populationSize];
crossover(parents,nextGen,parentsNumber,populationSize);
delete[] population;
population = new string[populationSize];
for(i=0;i<populationSize;i++) {
population[i] = nextGen[i];
}
delete[] nextGen;
}
ranking(population,outcome,populationSize,outcomeSize);
}
int main() {
srand(time(0));
int i;
int populationSize = 500;
int parentsNumber = populationSize - 5;
string * population = new string[populationSize];
generatePopulation(population,populationSize);
string vegetablesForPlanting[20];
genetic_algorithm(population, populationSize, parentsNumber,vegetablesForPlanting, 20);
cout << "Wynik:" <<endl;
for(i=0;i<20;i++) {
cout << vegetablesForPlanting[i] << endl;
}
return 0;
}