// random string using Genetic Algorithm
#include <queue>
#include <cstdlib>
#include <string>
#include <stack>
using namespace std;
#define MAX_VERTEX_NUM 30
#define POPULATION_SIZE 100
#define TARGET_SIZE 7</stack></string></cstdlib></queue></iostream>
bool visited[MAX_VERTEX_NUM];
double ve[MAX_VERTEX_NUM];
double vl[MAX_VERTEX_NUM];
stack<int> T;
// Valid Genes
vector<int> GENES = {2,2,2,2};</int></int>
typedef struct ArcNode{
int adjvex;
struct ArcNode* next;
double time;
bool key;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *first;
int machine;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum,arcnum;
int indegree[MAX_VERTEX_NUM];
}ALGraph;
ALGraph graph;
bool Visit(ALGraph G,int v)
{
printf("%d",G.vertices[v].data);
return true;
}
void dfs(ALGraph G,int v)
{
visited[v]=true;
Visit(G,v);
ArcNode* ptr;
for(ptr=G.vertices[v].first;ptr != nullptr;ptr=ptr->next)
{
if(!visited[ptr->adjvex])
dfs(G,ptr->adjvex);
}
}
void dfsTraverse(ALGraph G)
{
int v;
for(v=0;v<g.vexnum;v++) visited[v]="false;" for(v="0;v<G.vexnum;v++)" if(!visited[v])="" dfs(g,v);="" }="" void="" bfstraverse(algraph="" g)="" {="" for(int="" v="0;v<G.vexnum;v++)" queue<int=""> Q;
for(int v=0;v<g.vexnum;v++) {="" if(!visited[v])="" visited[v]="true;" visit(g,v);="" q.push(v);="" while(!q.empty())="" int="" m;="" m="Q.front();" q.pop();="" arcnode*="" ptr="G.vertices[m].first;" for(;ptr!="nullptr;ptr=ptr-">next)
{
if(!visited[ptr->adjvex])
{
visited[ptr->adjvex]=true;
Visit(G,ptr->adjvex);
Q.push(ptr->adjvex);
}
}
}
}
}
}</g.vexnum;v++)></g.vexnum;v++)>
void findIndegree(ALGraph& G)
{
int i,j,k;
for(int mm=0;mm<g.vexnum;mm++) g.indegree[mm]="0;" for(i="0;i<G.vexnum;i++)" {="" arcnode*="" arc="G.vertices[i].first;" for(;arc="" !="nullptr;arc=arc-">next)
{
G.indegree[arc->adjvex]++;
}
}
}</g.vexnum;mm++)>
bool TopologicalOrder(ALGraph G,stack<int>&tt)
{
//求各顶点事件的最早发生时间
int indegree[G.vexnum],count=0;
ArcNode* ptr;
findIndegree(G);
queue<int> S;
for(int ii=0;ii<g.vexnum;ii++) {="" if(g.indegree[ii]="=0)" s.push(ii);="" }="" for(int="" loop="0;loop<G.vexnum;loop++)" ve[loop]="0;" while(!s.empty())="" int="" jj="S.front();" s.pop();="" tt.push(jj);="" count++;="" ptr="G.vertices[jj].first;" for(;ptr="" !="nullptr;ptr=ptr-">next)
{
int k=ptr->adjvex;
if(--G.indegree[k]==0){
S.push(k);
}
if(ve[jj]+ptr->time>ve[k])
ve[k]=ve[jj]+ptr->time;
}
}
return count == G.vexnum;
}</g.vexnum;ii++)></int></int>
double criticalPath(ALGraph& G)
{
ArcNode* ptr;
int path=0,count=0;
double time=0;
for(int tt=0;tt<g.vexnum;tt++) {="" ptr="G.vertices[tt].first;" for(;ptr;ptr="ptr-">next)
{
ptr->time=0;
ptr->key= false;
}
}
if(!TopologicalOrder(G,T))
{
return false;
}
int i,k;
for(i=0;i<g.vexnum;i++) {="" vl[i]="ve[G.vexnum-1];" }="" while(!t.empty())="" int="" j="T.top();" t.pop();="" for(ptr="G.vertices[j].first;ptr;ptr=ptr-">next)
{
k=ptr->adjvex;
double dut=ptr->time;
if(vl[k]-dut<vl[j]) vl[j]="vl[k]-dut;" }="" for(i="0;i<G.vexnum;i++)" {="" for(ptr="G.vertices[i].first;ptr;ptr=ptr-">next)
{
k=ptr->adjvex;
double dut=ptr->time;
double ee=ve[i],el=vl[k]-dut;
char tag=(ee==el)?'*':' ';
if(tag=='*'){
ptr->key=true;
time+=ptr->time;
}
}
}
return time;
}</vl[j])></g.vexnum;i++)></g.vexnum;tt++)>
void Create_Graph(vector<int> gron)
{
int i,j,k;
int count=0;
ArcNode* ptr;
for(i=0;i<graph.vexnum;i++) {="" ptr="graph.vertices[i].first;" for(;ptr;ptr="ptr-">next)
{
ptr->time=gron[count];
count++;
}
}
}</graph.vexnum;i++)></int>
// Number of individuals in each generation
#define ITERATION_MAX 400
// Target string to be generated
//const int TARGET = 0;
// Function to generate random numbers in given range
int random_num(int start, int end)
{
int range = (end-start)+1;
int random_int = start+(rand()%range);
return random_int;
}
// Create random genes for mutation
int mutated_genes()
{
int len = GENES.size();
int r = random_num(0, len-1);
return GENES[r];
}
// create chromosome or string of genes
vector<int> create_gnome()
{
int len = TARGET_SIZE;
vector<int> gnome;
for(int i = 0;i<len;i++) gnome.push_back(mutated_genes());="" return="" gnome;="" }="" class="" representing="" individual="" in="" population="" {="" public:="" vector<int=""> chromosome;
double fitness;
Individual(vector<int> chromosome);
Individual mate(Individual parent2);
double cal_fitness();
};</int></len;i++)></int></int>
Individual::Individual(vector<int> chromosome)
{
this->chromosome = chromosome;
// Create_Graph();
fitness = cal_fitness();
};</int>
// Perform mating and produce new offspring
Individual Individual::mate(Individual par2)
{
// chromosome for offspring
vector<int> child_chromosome;</int>
int len = chromosome.size();
for(int i = 0;i<target_size;i++) {="" random="" probability="" float="" p="random_num(0," 100)="" 100;="" if="" prob="" is="" less="" than="" 0.45,="" insert="" gene="" from="" parent="" 1="" if(p="" <="" 0.45)="" child_chromosome.push_back(chromosome[i]);="" between="" 0.45="" and="" 0.90,="" 2="" else="" 0.90)="" child_chromosome.push_back(par2.chromosome[i]);="" otherwise="" gene(mutate),="" for="" maintaining="" diversity="" child_chromosome.push_back(mutated_genes());="" }="" create="" new="" individual(offspring)="" using="" generated="" chromosome="" offspring="" return="" individual(child_chromosome);="" };="" calculate="" fittness="" score,="" it="" the="" number="" of="" characters="" in="" string="" which="" differ="" target="" string.="" double="" individual::cal_fitness()="" create_graph(this-="">chromosome);
int i,j,k,count=0;
fitness=0;
for(i=0;i<graph.vexnum;i++) {="" graph.vertices[i].machine="chromosome[i];" arcnode*="" ptr="graph.vertices[i].first;" for(;ptr;ptr="ptr-">next)
{
ptr->time=graph.vertices[i].data*1.0/GENES[graph.vertices[i].machine];
}
}
fitness=criticalPath(graph);
return fitness;
};</graph.vexnum;i++)></target_size;i++)>
// Overloading < operator
bool operator<(const Individual &ind1, const Individual &ind2)
{
return ind1.fitness < ind2.fitness;
}
// Driver code
int main()
{
srand((unsigned)(time(nullptr)));
graph.vexnum=7;
graph.arcnum=9;
int m,n;
ArcNode* ptr;
int edge[9][2]={{0,1},{0,2},{1,3},{1,4},{2,3},{2,5},{3,5},{4,5},{5,6}};
int data[7]={1,3,4,5,6,3,0};
for(int i=0;i<graph.vexnum;i++) {="" graph.vertices[i].data="data[i];" graph.vertices[i].first="nullptr;" }="" for(auto="" &="" i="" :="" edge)="" m="i[0];" n="i[1];" ptr="(ArcNode*)malloc(sizeof(ArcNode));" ptr-="">adjvex=n;
ptr->next = graph.vertices[m].first;
graph.vertices[m].first=ptr;
}</graph.vexnum;i++)>
// criticalPath(graph);
// current generation
int generation = 0;
vector<individual> population;
bool found = false;</individual>
// create initial population
for(int i = 0;i<population_size;i++) {="" vector<int=""> gnome = create_gnome();
population.push_back(Individual(gnome));
}</population_size;i++)>
while(! found)
{
// sort the population in increasing order of fitness score
sort(population.begin(), population.end());
// if the individual having lowest fitness score ie.
// 0 then we know that we have reached to the target
// and break the loop
if(population[0].fitness <= 0||generation==4000)
{
found = true;
break;
}
// Otherwise generate new offsprings for new generation
vector<individual> new_generation;</individual>
// Perform Elitism, that mean 10% of fittest population
// goes to the next generation
int s = (10*POPULATION_SIZE)/100;
for(int i = 0;i<s;i++) new_generation.push_back(population[i]);="" from="" 50%="" of="" fittest="" population,="" individuals="" will="" mate="" to="" produce="" offspring="" s="(90*POPULATION_SIZE)/100;" for(int="" i="0;i<s;i++)" {="" int="" len="population.size();" r="random_num(0," 50);="" individual="" parent1="population[r];" parent2="population[r];" new_generation.push_back(offspring);="" }="" population="new_generation;" cout<<="" "generation:="" "="" <<="" generation="" "\t";="" "string:="" "<<="" population[0].chromosome="" <<"\t";="" "fitness:="" population[0].fitness="" "\n";="" generation++;="" ccc="0;" printf("\n*******************\n");="" ii="0;ii<graph.vexnum;ii++)" printf("%d*",graph.vertices[ii].machine);="" <="" code=""></s;i++)>