精华内容
下载资源
问答
  • 遗传算法实际应用

    2019-07-07 16:59:46
    根据demo简单编写一个求解某个函数的最大值的程序,从而理解下算法,会对每个步骤简单分析下。 主程序 clear all clc popsize=20; %群体大小 chromlength=10; %字符串长度(个体长度) pc=0.8; ...

    根据demo简单编写一个求解某个函数的最大值的程序,从而理解下算法,会对每个步骤简单分析下。

    主程序

    clear all
    clc 
    popsize=20; 							%群体大小  
    chromlength=10; 						%字符串长度(个体长度) 
    pc=0.8;   							%交叉概率
    pm=0.006;                                 %变异概率
    pop=initpop(popsize,chromlength);             %随机产生初始群体 
    for i=1:30                                  %30为迭代次数
    [objvalue]=calobjvalue(pop);                   %计算目标函数 
    fitvalue=calfitvalue(objvalue);                  %计算群体中每个个体的适应度
    [newpop]=selection(pop,fitvalue);               %复制 
    [newpop]=crossover(pop,pc);                   %交叉 
    [newpop]=mutation(pop,pc);                    %变异 
    [bestindividual,bestfit]=best(pop,fitvalue);		  %求出群体中适应值最大的个体及其适应值 
    y(i)=max(bestfit); 
    n(i)=i;  
    pop5=bestindividual;  
    x(i)=decodechrom(pop5,1,chromlength)*10/1023; 
    pop=newpop; 
    end  
    fplot('11*sin(7*x)-7*cos(3*x)',[0 11])
    hold on
    plot(x,y,'r*')
    hold off
    f=max(y)
    
    

    一、初始化
    1.首先执行的是初始化的程序 相当于就是随机初始化了一个以种群数为行数,具体编码个体的列数为主的随机初始化种群。
    其中roud主要起的作用是把随机数规范化为0-1,更符合我们使用。

    %初始化
    function pop=initpop(popsize,chromlength)  
    pop=round(rand(popsize,chromlength));  
    % rand随机产生每个单元为{0,1}行数为popsize,列数为chromlength的矩阵,
    % roud对矩阵的每个单元进行圆整。这样产生的初始种群。
    end
    
    

    二、进行迭代
    1、计算目标函数

    function [objvalue]=calobjvalue(pop)
    temp1=decodechrom(pop,1,10); %将pop每行转化成十进制数
    x=temp1*10/1023; %将二值域 中的数转化为变量域 的数
    objvalue=10*sin(5*x)+7*cos(4*x); %计算目标函数值
    end
    
    

    这里要先将二进制编码的数转化为十进制,就是使用普通的二进制的方法进行做的。

    %将二进制编码转换成十进制
    function pop2=decodechrom(pop,spoint,length)
    pop1=pop(:,spoint:spoint+length-1);
    pop2=decodebinary(pop1);
    end
    
    function pop2=decodebinary(pop)
    [px,py]=size(pop); 
    %求pop行和列数
    for i=1:py
    pop1(:,i)=2.^(py-i).*pop(:,i);
    end
    pop2=sum(pop1,2); 
    %求pop1的每行之和 
    end
    
    
    

    2.根据刚才得到的函数值来计算适应度。
    因为是求极大值 将小于0的数的适应度直接置为零,其他的函数值的地方直接当成适应度

    %计算个体的适应值  
    function fitvalue=calfitvalue(objvalue)
    global Cmin; %全局变量
    Cmin=0; 
    [px,py]=size(objvalue);
    for i=1:px
        if objvalue(i)+Cmin>0
            temp=Cmin+objvalue(i);
        else
            temp=0.0;
        end
        fitvalue(i)=temp;
    end
    fitvalue=fitvalue'
    
    

    3.选择复制
    首先计算适应度
    这得看你的排序选择策略是怎样的。
    一种排序是只对当代种群进行排序,这种排序选择方式并不包含精英保留策略的作用。
    另一种排序是把上一次种群放一直排序,这种方式包含了精英保留策略的作用。
    例如有初始种群包含个体为A1,A2,A3,A4,经过适应度计算后得知最优个体为顺序为A2,A1,A3,A4,经过排序选择后为A2,A2,A1,A3,然后经过交叉和变异后的变为B1,B2,B3,B4,而B1,B2,B3,B4的适应度均没有A2大,那么如果采用第一种排序方式,只对B1-B4排序选择,那么将丢失A2这一优良个体,所以并不包含精英保留作用。如果将B1-B4与A1-A2一起排序,那么由于A2适应度最大,因此必然会选到A2,等效于精英保留策略。

    %选择复制  
    function [newpop]=selection(pop,fitvalue)
    totalfit=sum(fitvalue); %求适应值之和
    fitvalue=fitvalue/totalfit; %单个个体被选择的概率
    fitvalue=cumsum(fitvalue); %如 fitvalue=[1 2 3 4],则 cumsum(fitvalue)=[1 3 6 10] 
    [px,py]=size(pop);
    ms=sort(rand(px,1)); %从小到大排列
    fitin=1;
    newin=1;
    while newin<=px
        if(ms(newin))<fitvalue(fitin)
            newpop(newin)=pop(fitin);
            newin=newin+1;
        else
            fitin=fitin+1;
        end
    end
    
    

    4.交叉

    %交叉  
    function [newpop]=crossover(pop,pc)
    [px,py]=size(pop);
    newpop=ones(size(pop));
    for i=1:2:px-1
        if(rand<pc)
            cpoint=round(rand*py);
            newpop(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)];
            newpop(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
        else
            newpop(i,:)=pop(i);
            newpop(i+1,:)=pop(i+1);
        end
    end  
    
    

    5.变异

    %变异  
    function [newpop]=mutation(pop,pm)
    [px,py]=size(pop);
    newpop=ones(size(pop));
    for i=1:px
        if(rand<pm)
            mpoint=round(rand*py);
            if mpoint<=0
                mpoint=1;
            end
            newpop(i)=pop(i);
            if any(newpop(i,mpoint))==0
                newpop(i,mpoint)=1;
            else
                newpop(i,mpoint)=0;
            end
        else
            newpop(i)=pop(i);
        end
    end
    
    

    6.求出适应度最大个体。

    %求出群体中适应值最大的值  
    function [bestindividual,bestfit]=best(pop,fitvalue)
    [px,py]=size(pop);
    bestindividual=pop(1,:);
    bestfit=fitvalue(1);
    for i=2:px
        if fitvalue(i)>bestfit
            bestindividual=pop(i,:);
            bestfit=fitvalue(i);
        end
    end
    
    
    展开全文
  • 遗传算法及其应用

    2013-05-28 16:11:37
    遗传算法及其应用的毕业设计,介绍了遗传算法和运用遗传算法解决实际问题
  • 遗传算法经常被应用于工业生产中的最优化问题当中,但是在面对非线性、多极值、多变量的问题时容易在早期寻优过程中陷入局部最优解范围.本文通过对传统的遗传算法添加灾变操作,减少了遗传算法常见的“早熟”现象,...
  • java遗传算法编程在实际中的应用,包括一个简单基本遗传算法的实现,机器人控制器上的应用、旅行商问题、以及排课问题 的java编码优秀代码
  • 一种改进的遗传算法及其应用,在实际中的使用,效果非常的好
  • 遗传算法应用(求解迷宫问题)

    万次阅读 2015-04-01 13:24:15
    遗传算法实际中的应用:求解迷宫问题

    遗传算法(Genetic Algorithm):

    是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

    遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。

    每个个体实际上是染色体(chromosome)带有特征的实体。

    染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

    因此,在一开始需要实现从表现型到基因型的映射即编码工作。

    由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。

    这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。


    遗传算法可以运用于迷宫的求解问题

    共包含6个文件(vs工程)

    CBobsMap.h文件

    #ifndef CBOBSMAP_H
    #define CBOBSMAP_H
    
    ///
    //
    //		File: CBobsMap.h
    //
    //		Author: Mat Buckland
    //
    //		Desc: Class for defining the map described in chapter 3
    //
    ///
    
    #include "stdlib.h"
    #include "windows.h"
    #include <vector>
    
    #include "defines.h"
    
    
    using namespace std;
    
    
    
    
    class CBobsMap
    {
    private:
    	
    	//storage for the map
    	static const int	map[MAP_HEIGHT][MAP_WIDTH];
    
    	static const int	m_iMapWidth;
    	static const int	m_iMapHeight;
    
    	//index into the array which is the start point
    	static const int	m_iStartX;
    	static const int	m_iStartY;
    
    	//and the finish point
    	static const int	m_iEndX;
    	static const int	m_iEndY;
    
    
    public:
    
    	//we can use this array as Bobs memory if rqd
    	int					memory[MAP_HEIGHT][MAP_WIDTH];
    
    	CBobsMap()
    	{
    		ResetMemory();
    
    	}
    
    	//takes a string of directions and see's how far Bob
    	//can get. Returns a fitness score proportional to the 
    	//distance reached from the exit.
    	double TestRoute(const vector<int> &vecPath, CBobsMap &memory);
    
    	//given a surface to draw on this function uses the windows GDI
    	//to display the map.
    	void Render(const int cxClient, const int cyClient, HDC surface);
    
    	//draws whatever path may be stored in the memory
    	void MemoryRender(const int cxClient, const int cyClient, HDC surface);
    
    	void ResetMemory();
    
    
    };
    
    
    
    #endif
    
    
    
    			



    CGABob.h

    #ifndef CGABOB_H
    #define CGABOB_H
    
    /
    //
    //		File: CGABob.h
    //
    //		Author: Mat Buckland
    //
    //		Desc: definition of the SGenome class and the genetic algorithm
    //			  class CGABob from chapter 3
    //
    /
    
    #include <vector>
    #include <sstream>
    
    #include "defines.h"
    #include "CBobsMap.h"
    #include "utils.h"
    
    using namespace std;
    
    
    
    //--------------------------------------------------------------
    //	define the genome structure
    //--------------------------------------------------------------
    struct SGenome
    {
    	vector<int> vecBits;
    	
    	double		dFitness;
    	
    
    	SGenome():dFitness(0){}
    	
    	SGenome(const int num_bits):dFitness(0)
    	{
    		//create a random bit string
    		for (int i=0; i<num_bits; ++i)
    		{
    			vecBits.push_back(RandInt(0, 1));
    		}
    	}
    };
    
    
    //--------------------------------------------------------------
    //	define the genetic algorithm class
    //---------------------------------------------------------------
    class CgaBob
    {
    private:
    
    	//the population of genomes
    	vector<SGenome>	m_vecGenomes;
    	
    	//size of population
    	int             m_iPopSize;
    
    	double          m_dCrossoverRate;
    	
    	double          m_dMutationRate;
    	
    	//how many bits per chromosome
    	int             m_iChromoLength;
    
    	//how many bits per gene
    	int             m_iGeneLength;
    	
    	int             m_iFittestGenome;
    	
    	double          m_dBestFitnessScore;
    	
    	double          m_dTotalFitnessScore;
    	
    	int             m_iGeneration;
    
    	//create an instance of the map class
    	CBobsMap        m_BobsMap;
    
    	//we use another CBobsMap object to keep a record of 
    	//the best route each generation as an array of visited
    	//cells. This is only used for display purposes.
    	CBobsMap		m_BobsBrain;
    
    	//lets you know if the current run is in progress.
    	bool			m_bBusy;
    	
    
    	
    	void        Mutate(vector<int> &vecBits);
    	
    	void        Crossover(const vector<int>	&mum,
                            const vector<int> &dad,
                            vector<int>       &baby1,
                            vector<int>       &baby2);
    	
    	SGenome&		RouletteWheelSelection();
    	
    	//updates the genomes fitness with the new fitness scores and calculates
      //the highest fitness and the fittest member of the population.
      void			  UpdateFitnessScores();
    
    	//decodes a vector of bits into a vector of directions (ints)
      vector<int>	Decode(const vector<int> &bits);
    	
    	//converts a vector of bits into decimal. Used by Decode.
      int				  BinToInt(const vector<int> &v);
    
    	//creates a start population of random bit strings
      void			  CreateStartPopulation();
    
    public:
    	
    	CgaBob(double cross_rat,
             double mut_rat,
             int    pop_size,
             int    num_bits,
             int    gene_len):m_dCrossoverRate(cross_rat),
                              m_dMutationRate(mut_rat),
                              m_iPopSize(pop_size),
                              m_iChromoLength(num_bits),
                              m_dTotalFitnessScore(0.0),
                              m_iGeneration(0),
                              m_iGeneLength(gene_len),
                              m_bBusy(false)
    		
    	{
    		CreateStartPopulation();
    	}
    	
    	void			Run(HWND hwnd);
    
    	void			Render(int cxClient, int cyClient, HDC surface);
    
      void			Epoch();
    	
    	//accessor methods
    	int				Generation(){return m_iGeneration;}
    	int				GetFittest(){return m_iFittestGenome;}
      bool      Started(){return m_bBusy;}
      void			Stop(){m_bBusy = false;}
    };
    
    
    
    #endif


    Defines.h
    #ifndef DEFINES_H
    #define DEFINES_H
    
    /
    //
    //		File:   Defines.h
    //
    //		Author: Mat Buckland
    //
    //		Desc:   #defines for the code project 'pathfinder'
    //
    /
    
    #define WINDOW_WIDTH	450
    #define WINDOW_HEIGHT	300
    
    #define MAP_WIDTH		15
    #define MAP_HEIGHT		10
    
    #define CROSSOVER_RATE	0.7
    #define MUTATION_RATE	0.001
    
    #define POP_SIZE		140
    #define CHROMO_LENGTH	70
    #define GENE_LENGTH		2
    
    #endif


    Utils.h


    #ifndef UTILS_H
    #define UTILS_H
    
    /
    //
    //		File: Utils.h
    //
    //		Author: Mat Buckland
    //
    //		Desc: useful utilities
    //
    /
    
    #include <stdlib.h>
    #include <math.h>
    #include <sstream>
    #include <string>
    
    using namespace std;
    
    //-----------------------------------------------------------------------
    //	some random number functions.
    //-----------------------------------------------------------------------
    inline int	  RandInt(int x,int y) {return rand()%(y-x+1)+x;}
    
    inline double RandFloat()		   {return (rand())/(RAND_MAX+1.0);}
    
    inline bool   RandBool()
    {
    	if (RandInt(0,1)) return true;
    
    	else return false;
    }
    
    //returns a random float in the range -1 < n < 1
    inline double RandomClamped()	   {return RandFloat() - RandFloat();}
    
    //-----------------------------------------------------------------------
    // useful string functions
    //-----------------------------------------------------------------------
    
    //int to string function
    string itos(int arg);
    
    
    
    
    #endif

    以下问cpp文件

    CBobsMap.cpp

    #include "CBobsMap.h"
    
    
    //this defines our little maze which Bob wanders
    //around in
    const int CBobsMap::map[MAP_HEIGHT][MAP_WIDTH] = 
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
     8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
     1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
     1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
     1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
     1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1,
     1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5,
     1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    
    
    const int CBobsMap::m_iMapHeight = MAP_HEIGHT;
    const int CBobsMap::m_iMapWidth  = MAP_WIDTH;
    
    const int CBobsMap::m_iStartX = 14;
    const int CBobsMap::m_iStartY = 7;
    
    const int CBobsMap::m_iEndX = 0;
    const int CBobsMap::m_iEndY = 2;
    
    
    //-------------------------------Render -----------------------------
    
    void CBobsMap::Render(const int cxClient,
    					  const int cyClient,
    					  HDC surface)
    {
    	const int border = 20;
    	
    	int BlockSizeX = (cxClient - 2*border)/m_iMapWidth;
    	int BlockSizeY = (cyClient - 2*border)/m_iMapHeight;
    
    	HBRUSH	BlackBrush, RedBrush, OldBrush;
    	HPEN	NullPen, OldPen;
    
    	//grab a null pen so we can see the outlines of the cells
    	NullPen = (HPEN)GetStockObject(NULL_PEN);
    
    	//grab a brush to fill our cells with
    	BlackBrush = (HBRUSH)GetStockObject(BLACK_BRUSH);
    
    	//create a brush for the exit/entrance points
    	RedBrush = CreateSolidBrush(RGB(255,0,0));
    
    	//select them into the device conext
    	OldBrush = (HBRUSH)SelectObject(surface, BlackBrush);
    	OldPen	 =	 (HPEN)SelectObject(surface, NullPen);
    	
    	for (int y=0; y<m_iMapHeight; ++y)
    	{
    		for (int x=0; x<m_iMapWidth; ++x)
    		{
    			//calculate the corners of each cell
    			int left  = border + (BlockSizeX * x);
    			int right = left + BlockSizeX;
    			
    			int top    = border + (BlockSizeY * y);
    			int bottom = top + BlockSizeY;
    			
    			//draw black rectangle if this is a wall
    			if (map[y][x] == 1)
    			{
    				SelectObject(surface, BlackBrush);
    
    				//draw the cell
    				Rectangle(surface, left, top, right, bottom);
    			}
    			
    			//draw red for exit and entrance
    			if ( (map[y][x] == 5) || (map[y][x] == 8))
    			{
    				SelectObject(surface, RedBrush);
    
    				//draw the cell
    				Rectangle(surface, left, top, right, bottom);
    			}
    			
    			
    		}
    	}
    
    	//restore the original brush
    	SelectObject(surface, OldBrush);
    
    	//and pen
    	SelectObject(surface, OldPen);
    }
    
    //-------------------------------MemoryRender ------------------------
    //
    //	//draws whatever path may be stored in the memory
    //--------------------------------------------------------------------
    void CBobsMap::MemoryRender(const int cxClient,
    							const int cyClient,
    							HDC surface)
    {
    	const int border = 20;
    	
    	int BlockSizeX = (cxClient - 2*border)/m_iMapWidth;
    	int BlockSizeY = (cyClient - 2*border)/m_iMapHeight;
    	
    	HBRUSH	GreyBrush, OldBrush;
    	HPEN	NullPen, OldPen;
    	
    	//grab a brush to fill our cells with
    	GreyBrush = (HBRUSH)GetStockObject(LTGRAY_BRUSH);
    
    	//grab a pen
    	NullPen = (HPEN)GetStockObject(NULL_PEN);
    	
    	//select them into the device conext
    	OldBrush = (HBRUSH)SelectObject(surface, GreyBrush);
    	OldPen	 =	(HPEN)SelectObject(surface, NullPen);
    	
    	for (int y=0; y<m_iMapHeight; ++y)
    	{
    		for (int x=0; x<m_iMapWidth; ++x)
    		{
    			//calculate the corners of each cell
    			int left  = border + (BlockSizeX * x);
    			int right = left + BlockSizeX;
    			
    			int top    = border + (BlockSizeY * y);
    			int bottom = top + BlockSizeY;
    			
    			//draw green rectangle if this is a wall
    			if (memory[y][x] == 1)
    			{
    				Rectangle(surface, left, top, right, bottom);
    			}
    		}
    	}
    	
    	//restore the original brush
    	SelectObject(surface, OldBrush);
    	
    	//and pen
    	SelectObject(surface, OldPen);
    
    }
    
    //---------------------------- TestRoute ---------------------------
    //
    //	given a decoded vector of directions and a map object representing
    //	Bob's memory, this function moves Bob through the maze as far as 
    //	he can go updating his memory as he moves.
    //-------------------------------------------------------------------
    double CBobsMap::TestRoute(const vector<int> &vecPath, CBobsMap &Bobs)
    {
    	int posX = m_iStartX;
    	int posY = m_iStartY;
    
    	for (int dir=0; dir<vecPath.size(); ++dir)
    	{
    		int NextDir = vecPath[dir];
    
    		switch(vecPath[dir])
    		{
    		case 0: //North
    
    			//check within bounds and that we can move
    			if ( ((posY-1) < 0 ) || (map[posY-1][posX] == 1) )
    			{
    				break;
    			}
    
    			else
    			{
    				posY -= 1;
    			}
    
    			break;
    
    		case 1: //South
    
    			//check within bounds and that we can move
    			if ( ((posY+1) >= m_iMapHeight) || (map[posY+1][posX] == 1) )
    			{
    				break;
    			}
    			
    			else
    			{
    				posY += 1;
    			}
    
    			break;
    
    		case 2: //East
    
    			//check within bounds and that we can move
    			if ( ((posX+1) >= m_iMapWidth ) || (map[posY][posX+1] == 1) )
    			{
    				break;
    			}
    			
    			else
    			{
    				posX += 1;
    			}
    
    			break;
    
    		case 3: //West
    
    			//check within bounds and that we can move
    			if ( ((posX-1) < 0 ) || (map[posY][posX-1] == 1) )
    			{
    				break;
    			}
    			
    			else
    			{
    				posX -= 1;
    			}
    
    			break;
    
    		}//end switch
    
    		//mark the route in the memory array
    		Bobs.memory[posY][posX] = 1;
    
    	}//next direction
    
    	//now we know the finish point of Bobs journey, let's assign
    	//a fitness score which is proportional to his distance from
    	//the exit
    
    	int	DiffX = abs(posX - m_iEndX);
    	int DiffY = abs(posY - m_iEndY);
    
    	//we add the one to ensure we never divide by zero. Therefore
    	//a solution has been found when this return value = 1
    	return 1/(double)(DiffX+DiffY+1);
    }
    
    //--------------------- ResetMemory --------------------------
    //
    //	resets the memory map to zeros
    //------------------------------------------------------------
    void CBobsMap::ResetMemory()
    {
    	for (int y=0; y<m_iMapHeight; ++y)
    	{
    		for (int x=0; x<m_iMapWidth; ++x)
    		{
    			memory[y][x] = 0;
    		}
    	}
    }
    
    
    

    CgaBob.cpp


    #include "CgaBob.h"
    
    
    
    //--------------------------RouletteWheelSelection-----------------
    //
    //	selects a member of the population by using roulette wheel 
    //	selection as described in the text.
    //------------------------------------------------------------------
    SGenome& CgaBob::RouletteWheelSelection()
    {
    	double fSlice	= RandFloat() * m_dTotalFitnessScore;
    	
    	double cfTotal	= 0.0;
    	
    	int	SelectedGenome = 0;
    	
    	for (int i=0; i<m_iPopSize; ++i)
    	{
    		
    		cfTotal += m_vecGenomes[i].dFitness;
    		
    		if (cfTotal > fSlice) 
    		{
    			SelectedGenome = i;
    			break;
    		}
    	}
    	
    	return m_vecGenomes[SelectedGenome];
    }
    
    //----------------------------Mutate---------------------------------
    //	iterates through each genome flipping the bits acording to the
    //	mutation rate
    //--------------------------------------------------------------------
    void CgaBob::Mutate(vector<int> &vecBits)
    {
    	for (int curBit=0; curBit<vecBits.size(); curBit++)
    	{
    		//do we flip this bit?
    		if (RandFloat() < m_dMutationRate)
    		{
    			//flip the bit
    			vecBits[curBit] = !vecBits[curBit];
    		}
    	}//next bit
    }
    
    //----------------------------Crossover--------------------------------
    //	Takes 2 parent vectors, selects a midpoint and then swaps the ends
    //	of each genome creating 2 new genomes which are stored in baby1 and
    //	baby2.
    //---------------------------------------------------------------------
    void CgaBob::Crossover( const vector<int> &mum,
    						const vector<int> &dad,
    						vector<int>		  &baby1,
    						vector<int>		  &baby2)
    {
    	//just return parents as offspring dependent on the rate
    	//or if parents are the same
    	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
    	{
    		baby1 = mum;
    		baby2 = dad;
    
    		return;
    	}
    	
    	//determine a crossover point
    	int cp = RandInt(0, m_iChromoLength - 1);
    
    	//swap the bits
    	for (int i=0; i<cp; ++i)
    	{
    		baby1.push_back(mum[i]);
    		baby2.push_back(dad[i]);
    	}
    
    	for (i=cp; i<mum.size(); ++i)
    	{
    		baby1.push_back(dad[i]);
    		baby2.push_back(mum[i]);
    	}
    }
    //-----------------------------------Run----------------------------------
    //
    //	This is the function that starts everything. It is mainly another 
    //	windows message pump using PeekMessage instead of GetMessage so we
    //	can easily and dynamically make updates to the window while the GA is 
    //	running. Basically, if there is no msg to be processed another Epoch
    //	is performed.
    //------------------------------------------------------------------------
    void CgaBob::Run(HWND hwnd)
    {
    	//The first thing we have to do is create a random population
    	//of genomes
    	CreateStartPopulation();
    	
    	m_bBusy = true;
    		
    }
    //----------------------CreateStartPopulation---------------------------
    //
    //-----------------------------------------------------------------------
    void CgaBob::CreateStartPopulation()
    {
    	//clear existing population
    	m_vecGenomes.clear();
    	
    	for (int i=0; i<m_iPopSize; i++)
    	{
    		m_vecGenomes.push_back(SGenome(m_iChromoLength));
    	}
    
    	//reset all variables
    	m_iGeneration		 = 0;
    	m_iFittestGenome	 = 0;
    	m_dBestFitnessScore  = 0;
    	m_dTotalFitnessScore = 0;
    }
    //--------------------------------Epoch---------------------------------
    //
    //	This is the workhorse of the GA. It first updates the fitness
    //	scores of the population then creates a new population of
    //	genomes using the Selection, Croosover and Mutation operators
    //	we have discussed
    //----------------------------------------------------------------------
    void CgaBob::Epoch()
    {
    	
    	UpdateFitnessScores();
    
    	//Now to create a new population
    	int NewBabies = 0;
    
    	//create some storage for the baby genomes 
    	vector<SGenome> vecBabyGenomes;
    
    	while (NewBabies < m_iPopSize)
    	{
    		//select 2 parents
    		SGenome mum = RouletteWheelSelection();
    		SGenome dad = RouletteWheelSelection();
    
    		//operator - crossover
    		SGenome baby1, baby2;
    		Crossover(mum.vecBits, dad.vecBits, baby1.vecBits, baby2.vecBits);
    
    		//operator - mutate
    		Mutate(baby1.vecBits);
    		Mutate(baby2.vecBits);
    
    		//add to new population
    		vecBabyGenomes.push_back(baby1);
    		vecBabyGenomes.push_back(baby2);
    
    		NewBabies += 2;
    	}
    
    	//copy babies back into starter population
    	m_vecGenomes = vecBabyGenomes;
    
    	//increment the generation counter
    	++m_iGeneration;
    }
    
    //---------------------------UpdateFitnessScores------------------------
    //	updates the genomes fitness with the new fitness scores and calculates
    //	the highest fitness and the fittest member of the population.
    //	Also sets m_pFittestGenome to point to the fittest. If a solution
    //	has been found (fitness == 1 in this example) then the run is halted
    //	by setting m_bBusy to false
    //-----------------------------------------------------------------------
    void CgaBob::UpdateFitnessScores()
    {
    	m_iFittestGenome		= 0;
    	m_dBestFitnessScore		= 0;
    	m_dTotalFitnessScore	= 0;
    
    	CBobsMap TempMemory;
    	 
    	//update the fitness scores and keep a check on fittest so far
    	for (int i=0; i<m_iPopSize; ++i)
    	{
    		//decode each genomes chromosome into a vector of directions
    		vector<int> vecDirections = Decode(m_vecGenomes[i].vecBits);
    
    		//get it's fitness score
    		m_vecGenomes[i].dFitness = m_BobsMap.TestRoute(vecDirections, TempMemory);
    
    		//update total
    		m_dTotalFitnessScore += m_vecGenomes[i].dFitness;
    
    		//if this is the fittest genome found so far, store results
    		if (m_vecGenomes[i].dFitness > m_dBestFitnessScore)
    		{
    			m_dBestFitnessScore = m_vecGenomes[i].dFitness;
    
    			m_iFittestGenome = i;
    
    			m_BobsBrain = TempMemory;
    
    			//Has Bob found the exit?
    			if (m_vecGenomes[i].dFitness == 1)
    			{
    				//is so, stop the run
    				m_bBusy = false;
    			}
    		}
    
    		TempMemory.ResetMemory();
    	
    	}//next genome
    }
    
    //---------------------------Decode-------------------------------------
    //
    //	decodes a vector of bits into a vector of directions (ints)
    //
    //	0=North, 1=South, 2=East, 3=West
    //-----------------------------------------------------------------------
    vector<int> CgaBob::Decode(const vector<int> &bits)
    {
    	vector<int>	directions;
    
    	//step through the chromosome a gene at a time
    	for (int gene=0; gene < bits.size(); gene += m_iGeneLength)
    	{
    		//get the gene at this position
    		vector<int> ThisGene;
    		
    		for (int bit = 0; bit < m_iGeneLength; ++bit)
    		{
    			ThisGene.push_back(bits[gene+bit]);
    		}
    
    		//convert to decimal and add to list of directions
    		directions.push_back(BinToInt(ThisGene));
    	}
    
    	return directions;
    }
    
    //-------------------------------BinToInt-------------------------------
    //	converts a vector of bits into an integer
    //----------------------------------------------------------------------
    int	CgaBob::BinToInt(const vector<int> &vec)
    {
    	int val = 0;
    	int multiplier = 1;
    	
    	for (int cBit=vec.size(); cBit>0; cBit--)
    	{
    		val += vec[cBit-1] * multiplier;
    		
    		multiplier *= 2;
    	}
    
    	return val;
    }
    
    
    
    //------------------------- Render -------------------------------
    //
    //	given a surface to render to this function renders the map
    //	and the best path if relevant. cxClient/cyClient are the 
    //	dimensions of the client window.
    //----------------------------------------------------------------
    void CgaBob::Render(int cxClient, int cyClient, HDC surface)
    {
    	//render the map
    	m_BobsMap.Render(cxClient, cyClient, surface);
    
    	//render the best route
    	m_BobsBrain.MemoryRender(cxClient, cyClient, surface);
    
    	//Render additional information
    	string s = "Generation: " + itos(m_iGeneration);
    	TextOut(surface, 5, 0, s.c_str(), s.size());
    	
    	if (!m_bBusy)
    	{
    		string Start = "Press Return to start a new run";
    		
    		TextOut(surface, cxClient/2 - (Start.size() * 3), cyClient - 20, Start.c_str(), Start.size());
    	}
    	
    	else
    		
    	{
    		string Start = "Space to stop";
    		
    		TextOut(surface, cxClient/2 - (Start.size() * 3), cyClient - 20, Start.c_str(), Start.size());
    	}
    	
    }
    


    utils.cpp
    #include "utils.h"
    
    
    //--------------------------itos------------------------------------
    //	converts an integer to a string
    //------------------------------------------------------------------		
    string itos(int arg)
    {
        ostringstream buffer;
    	
    	//send the int to the ostringstream
        buffer << arg;	
    	
    	//capture the string
        return buffer.str();		
    }

    mian.cpp

    //#define WIN32_LEAN_AND_MEAN
    
    #include <windows.h>   
    #include <stdlib.h>
    #include <time.h>
    
    #include "CgaBob.h"
    #include "defines.h"
    
    using namespace std;
    
    
    
    ///GLOBALS 
    
    char*			szApplicationName = "Chapter3 - Pathfinder";
    char*			szWindowClassName = "PFclass";
    
    //pointer to the GA object
    CgaBob*	g_pGABob;
    
    
    //-----------------------------------WinProc------------------------------------------
    //
    //------------------------------------------------------------------------------------
    LRESULT CALLBACK WindowProc(HWND hwnd, 
    						    UINT msg, 
                                WPARAM wparam, 
                                LPARAM lparam)
    {
    	//device context for our window
    	HDC				hdc;	
    	PAINTSTRUCT     ps;
    
    	//these hold the dimensions of the client window area
    	static int cxClient, cyClient;
    
    	//used to create the back buffer
    	static HDC		hdcBackBuffer;
    	static HBITMAP	hBitmap;
    	static HBITMAP	hOldBitmap;
    						  
    
    	switch(msg)
    	{	
        case WM_CREATE: 
    		{
    			//seed the random number generator
    			srand((unsigned) time(NULL));
    
    			//create the GA class
    			g_pGABob = new CgaBob(CROSSOVER_RATE,
    								            MUTATION_RATE,
    							            	POP_SIZE,
    								            CHROMO_LENGTH,
    								            GENE_LENGTH);
    			
    			//get the size of the client window
    			RECT rect;
    			GetClientRect(hwnd, &rect);
    
    			cxClient = rect.right;
    			cyClient = rect.bottom;
    
    			//create a surface for us to render to(backbuffer)
    			hdcBackBuffer = CreateCompatibleDC(NULL);
    
    			HDC hdc = GetDC(hwnd);
    
    			hBitmap = CreateCompatibleBitmap(hdc,
    											 cxClient,
    											 cyClient);
    
    			ReleaseDC(hwnd, hdc);
    
    			hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);
    
    
    		} 
    			
    		break;
    		//check key press messages
    		case WM_KEYUP:
    		{
    			switch(wparam)
    			{
    				case VK_RETURN:
    				{
    					g_pGABob->Run(hwnd);
    
    				}
    					
    				break;
    
    				case VK_ESCAPE:
    				{
    					PostQuitMessage(0);
    				}
    
    				break;
    
    				case VK_SPACE:
    					{
    						g_pGABob->Stop();
    					}
    					
    					break;
    
    				
    			}//end switch
    		}
    
    		break;
    
    		//has the user resized the client area?
    		case WM_SIZE:
    		{
    			cxClient = LOWORD(lparam);
    			cyClient = HIWORD(lparam);
    
    			//resize the backbuffer accordingly
    			SelectObject(hdcBackBuffer, hOldBitmap);
    
    			HDC hdc = GetDC(hwnd);
    
    			hBitmap = CreateCompatibleBitmap(hdc,
    											cxClient,
    											cyClient);
    
    			ReleaseDC(hwnd, hdc);
    			
    			hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);
    		} 
    
    		break;
      
    		case WM_PAINT: 
    		{
    
    			hdc = BeginPaint(hwnd, &ps);
    			
    			//fill our backbuffer with white
    			BitBlt(hdcBackBuffer, 0, 0, cxClient, cyClient, NULL, NULL, NULL, WHITENESS);
    			
    			//render the map and best route
    			g_pGABob->Render(cxClient, cyClient, hdcBackBuffer);
    			
    			//now blit backbuffer to front
    			BitBlt(hdc, 0, 0, cxClient, cyClient, hdcBackBuffer, 0, 0, SRCCOPY);
    
    			ReleaseDC(hwnd, hdc);
    			
    			EndPaint(hwnd, &ps);
    		} 
    			
    		break;
    
    		case WM_DESTROY: 
    		{
    			
    			SelectObject(hdcBackBuffer, hOldBitmap);
    			
    			//clean up our backbuffer objects
    			DeleteDC(hdcBackBuffer);
    			DeleteObject(hBitmap);
    
    			//delete our GA object
    			delete g_pGABob;
    
    			// kill the application, this sends a WM_QUIT message 
    			PostQuitMessage(0);
    
       		} 
    			
    		break;
    
    		default:break;
    
    	}//end switch
    
    	// default msg handler 
    	return (DefWindowProc(hwnd, msg, wparam, lparam));
    
    }//end WinProc
    
    
    //-----------------------------------WinMain-----------------------------------------
    //	Entry point for our windows application
    //-----------------------------------------------------------------------------------
    int WINAPI WinMain(	HINSTANCE hinstance,
    					HINSTANCE hprevinstance,
    					LPSTR lpcmdline,
    					int ncmdshow)
    {
    
    	WNDCLASSEX winclass; 
    	HWND	   hwnd;	 
    	MSG		   msg;		 
    
    	// first fill in the window class stucture
    	winclass.cbSize         = sizeof(WNDCLASSEX);
    	winclass.style			    = CS_HREDRAW | CS_VREDRAW;
    	winclass.lpfnWndProc	  = WindowProc;
    	winclass.cbClsExtra		  = 0;
    	winclass.cbWndExtra		  = 0;
    	winclass.hInstance		  = hinstance;
    	winclass.hIcon			    = LoadIcon(NULL, IDI_APPLICATION);
    	winclass.hCursor		    = LoadCursor(NULL, IDC_ARROW); 
    	winclass.hbrBackground	= NULL; 
    	winclass.lpszMenuName	  = NULL;
    	winclass.lpszClassName	= szWindowClassName;
    	winclass.hIconSm        = LoadIcon(NULL, IDI_APPLICATION);
    
    
    	// register the window class
    	if (!RegisterClassEx(&winclass))
    		return 0;
    
    	// create the window
    	if (!(hwnd = CreateWindowEx(NULL,									
    								szWindowClassName,						
    								szApplicationName,						
    								WS_OVERLAPPEDWINDOW | WS_VISIBLE,
    					 			0,0,									
    								WINDOW_WIDTH,WINDOW_HEIGHT,				
    								NULL,									
    								NULL,								
    								hinstance,								
    								NULL)))									
    	return 0;
    
    	ShowWindow(hwnd, ncmdshow);
    	UpdateWindow(hwnd);
    
    	//enter the message loop
    	bool bDone = false;
    
    	while(!bDone)
    	{
    					
    		while( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) 
    		{
    			if( msg.message == WM_QUIT ) 
    			{
    				// Stop loop if it's a quit message
    				bDone = true;
    			} 
    
    			else 
    			{
    				TranslateMessage( &msg );
    				DispatchMessage( &msg );
    			}
    		}
    		
        //if the user has started the run update the GA and display
        //accordingly
        if (g_pGABob->Started())
        {
    	    //update the gun
          g_pGABob->Epoch();
    
    	    //this will call WM_PAINT 
    	    InvalidateRect(hwnd, NULL, TRUE);
    		  UpdateWindow(hwnd);
        }
    					
    					
    	}//end while
    	
    
      UnregisterClass( szWindowClassName, winclass.hInstance );
     
                 
      return 0;                                   
                 
    
    } // end WinMain
    
    
    

    运行截图



    参考资料:

    遗传算法

    展开全文
  • 很好的讲述遗传算法的书籍,讲述如何用遗传算法解决实际问题
  • 实际工程中常见的拱形桁架,取其整体重量为目标函数,以桁架的拱高、厚度和各杆件的截面特征为设计变量,以杆件应力、稳定性和节点位移为约束条件,依据遗传算法的基本理论进行优化计算,并对计算过程和结果进行了...
  • 第五章至第七章介绍英国设菲尔德(Sheffield)大学的MATLAB遗传算法工具箱及其使用方法,举例说明如何利用遗传算法工具箱函数编写求解实际优化问题的MATLAB程序。第八章和第九章介绍MathWorks公司最新发布的MATLAB...
  • 遗传算法原理及应用实例

    热门讨论 2010-04-10 14:35:51
    遗传算法是一种用来解决需要搜索复杂解空间的问题的 启发式算法。它通常包含了一系列的参数。如交叉运算和变异运 算的参数,种群的大小以及不同的...实际的优化问题找到相应的遗传算法的最佳结构将是非常重要 的问题。
  • 噪声环境下遗传算法的有效实现对于提高遗传算法实际应用价值具有非常重要的意义。文中对遗传算法领域的噪声环境以及噪声模型进行了分析和描述,着重从函数优化和模式定理分析了噪声环境对遗传算法的影响和主要原因,...
  • 针对标准遗传算法实际应用中存在的问题 ,设计了简单遗传算法的一种改进形式——加速遗传算法 ( AGA) ,并对 AGA的有效性和可行性进行了理论分析和实例分析 .
  • 遗传算法

    千次阅读 2017-04-01 22:25:45
    算法实际应用中的问题 GA的C和python实现 遗传算法(Genetic Algorithm)是由美国的J.Holland教授于1975年首先提出。它是模拟达尔文进化理论和自然界优胜劣汰的机制进行全局最优解搜索的启发式优化算法。遗传算法从...

    遗传算法


           遗传算法(Genetic Algorithm)是由美国的J.Holland教授于1975年首先提出。它是模拟达尔文进化理论和自然界优胜劣汰的机制进行全局最优解搜索的启发式优化算法。遗传算法从问题的一个种群(可行解)开始,种群中的每个个体都具有基因编码,代表了个体的特征,也决定了个体在自然界中的表现,也就是个体的适应度。自然界中的基因编码与组合十分复杂,在遗传算法用于实际问题的求解中我们往往对基因的编码过程进行简化,例如进行二进制编码。在产生初代种群后,GA根据个体的适应度模拟自然选择,并通过个体间基因的交叉和变异产生新的种群。这个过程的不断迭代更新保证后产生的种群将比之前的种群具有更高的适应度,最终产生的具有最高适应度的个体通过解码就将作为问题的近似解。


    GA的特点

    • 直接对结构对象操作,无需函数求导和连续性的限定
    • 全局搜索能力强
    • 自适应的调整搜索方向和搜索空间
    • 可并行

    GA流程图

    Created with Raphaël 2.1.0初始化个体评价选择、交叉、变异是否满足终止条件?Endyesno

    GA算法基本过程

    1. 初始化:设置最大迭代进化次数T,随机生成M个个体作为初始种群P(0);
    2. 个体评价:计算当前种群P(t)中的个体适应度;
    3. 选择:在个体评价之后,对群体进行选择操作目的是将优秀个体的基因通过组合配对交叉遗传到下一代种群中;
    4. 交叉:遗传算法中的核心部分;
    5. 变异:在个体基因的基础上进行变动,模拟自然界的基因突变,其变异结果的好坏不定;
    6. 终止条件:若迭代次数达到预先设定的T,将迭代过程中具有最优适应度的个体作为问题的解输出。

    GA算法具体步骤分析

           遗传算法的核心是个体之间的组合交叉变异部分。个体之间的组合交叉变异方式众多,不同的交叉变异方式将对算法的效率产生巨大的影响。

    选择

    • 适应度比例方法,例如轮盘赌选择算法
    • 随机遍历抽样
    • 局部选择

           其中轮盘赌选择算法是最简单也是最常用的选择算法之一。该方法中各个个体被选择的概率和其适应度成正比。个体的适应度越高,其被选择到的概率越大。

    交叉

    • 实值重组:离散重组、中间重组、线性重组、扩展线性重组
    • 二进制交叉:单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉

           其中单点交叉是最常用的交叉算法。在操作时首先设定一个交叉点,将两个个体在该点之后的基因结构进行互换,从而形成两个新的个体。例如:
    个体A:1 0 0 1 ↑ 1 1 1 → 1 0 0 1 0 0 0 新个体
    个体B:0 0 1 1 ↑ 0 0 0 → 0 0 1 1 1 1 1 新个体

    变异

    • 实值变异
    • 二进制变异

           遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时,利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然,此种情况下的变异概率应取较小值,否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性,以防止出现未成熟收敛现象。此时收敛概率应取较大值。


    GA与传统优化算法的区别

    • 遗传算法的初始解设置为一个群体,搜索覆盖面广,不易陷入局部最优;
    • 变异部分使得算法有一定概率跳出局部最优;
    • 遗传算法可同时对多个可行解进行实用性评估,算法容易并行;
    • 具有自组织、自适应、自学习性。算法利用自身组织架构进行搜索,适应度大的个体具有较高存活率,指导了最优解的搜索方向。

    算法的经典应用

    1. 旅行商问题(Traveling Salesman Problem,TSP):TSP是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。
    2. 指派问题(Assignment problem):在满足特定指派要求条件下,使指派方案总体效果最佳。如:有若干项工作需要分配给若干人(或部门)来完成。
    3. 单车间调度问题(Job-shop scheduling problem, JSP)是最基本最著名的调度问题,也是NP难问题,无最优解精确算法。一般类型的JSP问题可表达为:n个工件在m台机器上加工,每个工件有特定的加工工艺,每个工件加工的顺序及每道工序所花时间给定,安排工件在每台机器上工件的加工顺序,使得某种指标最优。
    4. 运输问题:为了把某种产品从若干个产地调运到若干个销地,已知每个产地的供应量和每个销地的需求量,如何在许多可行的调运方案中,确定一个总运输费或总运输量最少的方案。
    5. 背包问题(Transportation problem):给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。
    6. 设施选址问题(Facility Location Problem):指在给定的若干位置中选择一些来建立设施使得所有顾客的需求得到满足,且总体费用最小。
    7. 图划分问题(Graph Partitioning Problem):将图中的节点划分为数量大致相等的若干个分区,使得两个顶点分别在不同分区的边的数量最小化。
    8. 图着色问题。对于n个顶点的无环图G,要求对其各个顶点进行着色,使得任意相邻的顶点都有不同的颜色,且所用颜色种类最少。

    算法实际应用中的问题

    1.算法容易过早收敛,且在GA的轮盘赌选择算法中根据个体的适应度进行基因的优选,但是如果前期存在超级个体,几乎所有的交叉产生的子代都存在这个超级个体的基因,因此失去了种群的多样性;但是在种群迭代的后期当所有的个体适应度都差不多的时候,算法接近于随机搜索,效率降低。
    - 优化方案:适应度放缩。前期,当适应度差距较大的时候,将适应度适当缩小,适应度较小的个体也可以被选择,同时不存在超级个体,使得种群不那么容易“早熟”;后期,当适应度接近的时候,将适应度进行适当扩大,即扩大个体间的差异,使得算法在后期依然有选择作用。例如:f(x)af(x)+b

    2.算法的搜索效率相对于一些其他的优化算法较低。
    3.遗传算法对算法的精度、可行度、计算复杂性等方面,还没有有效的定量分析方法。


    GA的C++和python实现

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<time.h>
    
    #define num_pop 100      //定义初始种群数目
    #define num_iter 1000     //定义迭代次数
    #define p_cross 0.7      //定义交叉概率
    #define p_mutate 0.2     //定义变异概率
    #define len_chrom 1000   //染色体长度
    
    double pop[num_pop][len_chrom];     //种群数组
    double fitness[num_pop];            //种群中个体的适应度
    double fitness_prob[num_pop];       //每个个体被选中的概率(轮盘赌)
    double lbest[num_iter];             //每次迭代中的最优适应度
    double gbest;                       //全局最优个体的适应度
    double gbest_pos[len_chrom];        //全局最优个体的位置
    double average_best[num_pop + 1];   //每一代平均适应度
    int gbest_index;                    //取得最优值的迭代次数序号
    
    using namespace std;
    
    //适应度函数
    double fit(double a[]){
        double cost = 0;
        for(int i = 1; i < len_chrom; i++){
            cost += (a[i] - 0.5)*(a[i] - 0.5);
    //      cost += a[i] * a[i];
        }
        return cost;
    }
    
    // 求和函数
    double sum(double * fitness)     //对每一代中所有个体的适应度进行求和
    {
        double sum_fit = 0;
        for(int i = 0; i < num_pop; i++){
            sum_fit += *(fitness+i);
        }
        return sum_fit;
    }
    
    // 求最小值函数
    double * min(double * fitness)            //返回一个长度为2的数组,第一个为最小适应度代表的个体的指标,第二个为最小适应度
    {
        double min_fit = *fitness;
        double min_index = 0;
        static double arr[2];
        for(int i = 1; i < num_pop; i++){
            if( *(fitness+i) < min_fit ){
                min_fit = *(fitness + i);
                min_index = i;
            }
        }
        arr[0] = min_index;
        arr[1] = min_fit;
        return arr;
    }
    
    //种群初始化
    void initial(){
        for(int i = 0; i < num_pop; i++){          //随机初始化种群位置
            for(int j = 0; j < len_chrom; j++){
                pop[i][j] = 1.0*rand()/RAND_MAX;
            }
            fitness[i] = fit(pop[i]);              //初始化适应度
        }
    //    for(int i = 0; i < num_pop; i++){         
    //        for(int j = 0; j < len_chrom; j++)
    //            printf("%f", pop[i][j]);
    //  }
    
    }
    
    //选择操作
    void Select(double pop[num_pop][len_chrom]){
        int index[num_pop];
        for(int i = 0; i < num_pop; i++){
            double * arr = pop[i];
            fitness[i] = 1 / fit(arr);          //这里函数值越小,目标适应度越大   
        }
        double sum_fitness = 0;
        for(int i = 0; i < num_pop; i++){
            sum_fitness += fitness[i];          //适应度求和
        }
        for(int i = 0; i < num_pop; i++){      //轮盘赌选择中,适应度越大的个体越容易被选中
            fitness_prob[i] = fitness[i] / sum_fitness;
        }
        for(int i = 0; i < num_pop; i++){      //恢复原先的适应度函数值
            fitness[i] = 1.0 / fitness[i];            
        }
    
        for(int i = 0; i < num_pop; i++){      //轮盘赌选择个体
            double pick = 1.0*rand()/RAND_MAX;
            while(pick < 0.0001)
                pick = 1.0* rand()/RAND_MAX;
            for(int j = 0; j < num_pop; j++){ 
                pick = pick - fitness_prob[j];
                if(pick <= 0){
                    index[i] = j;
                    break;
                }
            }
        }
        for(int i = 0; i < num_pop; i++){
            for(int j = 0; j < len_chrom; j++){
                pop[i][j] = pop[index[i]][j];
            }
            fitness[i] = fitness[index[i]];
        }
    }
    
    //交叉操作
    void Cross(double pop[num_pop][len_chrom]){
        for(int i = 0; i < num_pop; i++){              //随机选择两个个体进行交叉
            double pick1 = 1.0*rand()/RAND_MAX;
            double pick2 = 1.0*rand()/RAND_MAX;
            int choice1 = (int)(pick1*num_pop);        //第一个随机选取的染色体序号
            int choice2 = (int)(pick2*num_pop);        //第二个随机选取的染色体序号
            while(choice1 > num_pop - 1){              //防止选取位置过界
                pick1 = 1.0*rand()/RAND_MAX;
                choice1 = (int)(pick1*num_pop); 
            }
            while(choice2 > num_pop - 1){
                pick2 = 1.0*rand()/RAND_MAX;
                choice2 = (int)(pick2*num_pop);
            }
            double pick = 1.0*rand()/RAND_MAX;   //用于判断是否进行交叉操作
            if(pick > p_cross)
                continue;
    
            pick = 1.0*rand()/RAND_MAX;
            int pos = (int)(pick*len_chrom);
            while(pos > len_chrom - 1){                 //防止越界
                double pick = 1.0*rand()/RAND_MAX;
                pos = (int)(pick*len_chrom); 
            }
    
            double r = 1.0*rand()/RAND_MAX;       //交叉开始
            double v1 = pop[choice1][pos];
            double v2 = pop[choice2][pos];
            pop[choice1][pos] = r*v2 + (1-r)*v1;
            pop[choice2][pos] = r*v1 + (1-r)*v2;         //交叉结束
        }
    }
    
    //变异
    void Mutate(double pop[num_pop][len_chrom]){
        for(int i = 0; i < num_pop; i++){
            double pick = 1.0*rand()/RAND_MAX;  //随机选择一个染色体进行变异
            int choice = (int)(pick*num_pop);
            while(choice > num_pop - 1){                 //防止越界
                pick = 1.0*rand()/RAND_MAX;
                choice = (int)(pick*num_pop);  
            }
            pick = 1.0*rand()/RAND_MAX;          //用于决定该轮是否进行变异
            if(pick > p_mutate)
                continue;
            pick = 1.0*rand()/RAND_MAX;
            int pos = (int)(pick*len_chrom);
            while(pos > len_chrom-1){                  //防止越界
                pick = 1.0*rand()/RAND_MAX;
                pos = (int)(pick*len_chrom);
            }
            pop[i][pos] = 1 - pop[i][pos];             //变异规则
        }
    }
    
    
    //主函数
    int main(){
        time_t start, finish;
        start = clock();                    //开始时间
        srand((unsigned)time(NULL));        //初始化随机数种子
        initial();                          //种群初始化
        double * best_fit_index = min(fitness);     //初始时最优适应度的个体和它的适应度
        int best_index =(int)(*best_fit_index);     //转换为int
        gbest = *(best_fit_index+1);                //最优适应度
        gbest_index = 0;                            //取得最优适应度的迭代次数,初始为0
        average_best[0] = sum(fitness)/num_pop;     //初始化平均适应度
        for(int i = 0; i < len_chrom; i++){        //将初始时的具有最优适应度的个体的位置传给gbest_pos
            gbest_pos[i] = pop[best_index][i];
        }
    
        for(int i = 0; i < num_pop; i++){       //迭代开始
            Select(pop);                        //选择
            Cross(pop);                         //交叉
            Mutate(pop);                        //变异
            for(int j = 0; j < num_pop; j++){   //计算此代的每个个体的适应度
                fitness[j] = fit(pop[j]);
            }
            double sum_fit = sum(fitness);      //此代个体的适应度总和
            average_best[i + 1] = sum_fit / num_pop;   //此代的个体平均适应度
            double * arr = min(fitness);        //新一代最优个体二维数组
            double new_best = *(arr+1);         //新一代最优值
            int new_best_index = (int)(*arr);   //新一代最优值序号
            if(new_best < gbest){               //若新一代个体最优适应度更小,那么更新
                gbest = new_best;
                for(int j = 0; j < len_chrom; j++){
                    gbest_pos[j] = pop[new_best_index][j];
                }
                gbest_index = i + 1;
            }
        }
    
        finish = clock();                   //结束时间
        double duration = ((double)(finish-start))/CLOCKS_PER_SEC;    //程序运行时间,以秒为单位
        printf("程序计算耗时:%lf秒\n.",duration);
        printf("遗传算法进化了%d次,最优值为:%lf,最优值在第%d代取得,此代的平均最优值为%lf.\n",num_iter,gbest,gbest_index,average_best[gbest_index]);
        return 0;
    }
    
    展开全文
  • 遗传算法基本原理及实际应用,实际问题分析。
  • 自适应遗传算法在燃油运输问题上的应用,崔雪源,赵东方,传统遗传算法中的交叉和变异概率是固定的,而这两个参数的选取对遗传算法的求解结果和求解效率都有一定的影响,在遗传算法实际
  • 遗传算法 禁忌搜索这些智能优化算法,在实际工程中有成功应用或大规模应用吗?是不是忽悠人、水论文的?

    遗传算法 禁忌搜索这些智能优化算法,在实际工程中有成功应用或大规模应用吗?是不是忽悠人、水论文的?

    展开全文
  • 但是在实际应用中,有的模块太大或输入参数太多,等价类划分后需要进行的测试工作可能是一个极大的任务。这时,如何选择最优的测试用例就成为测试人员的一个重要任务。 遗传算法是模仿生物遗传和进化机制的一种最...
  • 第五章至第七章介绍英国设菲尔德(Sheffield)大学的MATLAB遗传算法工具箱及其使用方法,举例说明如何利用遗传算法工具箱函数编写求解实际优化问题的MATLAB程序。第八章和第九章介绍MathWorks公司最新发布的MATLAB...
  • 遗传算法GA(Genetic Algorithm)与模拟退火算法SA(Simulated Annealing)相结合,提出模拟退火遗传算法(SAGA),并将其应用于MC-CDMA无线通信系统的多用户检测技术中,以求降低多用户检测算法在实际应用中的复杂度并...
  • 是一本关于遗传算法的原理和实际应用的完整教材。希望对学习者有所帮助。
  • 最近看到之前做的项目,是关于使用遗传算法实现智能组卷的。所以这次为大家分享遗传算法的基本原理,以及在实际场景中的应用。 "揭开算法神秘的面纱" ...对于算法的学习,应该更有规划,了解算法的实际应用
  • 论文研究-多重群体遗传算法的特点及应用.pdf, 建立了多重群体遗传算法模型并成功地用于实际研究工作。多重群体遗传算法采用了标准化的独立的基因/染色体模型及由种群和...
  • 遗传算法的运行过程中,它不对所求解问题的实际决策变量直接进行操作,而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算,通过这种遗传操作来达到优化的目的,这是遗传算法的特点之一。遗传算法通过...
  • 很详细的介绍遗传算法的书 还有实际操作哟
  • 遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型,从代表问题可能潜在解集的一个种群开始,种群由经过基因编码的一定数目的个体组成。每个个体...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 553
精华内容 221
关键字:

遗传算法实际应用