---

编译环境下载

C/C++编译环境

codeblocks ： https://pan.baidu.com/s/14Xx2if5d1h4ayUEZA3Vl4g

java编译环境

先装java运行环境： https://pan.baidu.com/s/1ptvjPbYHZvdjxs_0K0e5cA

再装eclipse：https://pan.baidu.com/s/1L2LUWoECSL-pp_tauu9-xw

代码下载

code_course： https://pan.baidu.com/s/10ZTldvV5snnb4AWpvkJkXA

---

遗传算法求解函数最值问题

/****************************************/
//功能：使用遗传算法求解y = -x^2 + 5的最大值
//遗传算法细节：
//编码：二进制
//选择：轮转赌轮
//交叉：单点交叉，交叉概率固定
//变异：平均随机变异，变异概率固定
//具体参数可以事先给定

/****************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <cmath>

using namespace std;

/*****初始化一些参数*****/
const int Population_size = 100;        //种群规模
const int Chromosome_length = 6;    //2^6   假定有64个网络节点，用64位表示每一个节点
double rate_crossover = 0.5;                //交叉率
double rate_mutation = 0.001;           //变异率
int iteration_num = 50;                     //进化50代
/****************************************/

//将染色体定义为结构体类型
typedef struct Chromosome
{
    short int bit[Chromosome_length];        //染色体二进制码串
    double value;                            //二进制代码对应的实际值
    double fitness;                          //适应值
    double rate_fit;                         //相对的fit值，即所占的百分比
    double cumu_fit;                         //积累概率
}chromosome;


/*****函数声明*****/
//初始化得到个体的二进制字符串
void population_initialize(chromosome (&population_current)[Population_size]);
//对染色体进行解码
void decode(chromosome &population_current) ;
//计算染色体的适应度值
double objective_function(double x);
//更新种群内个体的属性值
void fresh_property(chromosome(&population_current)[Population_size]);
//基于旋转赌轮的选择操作    proportional roulette wheel selection
void seletc_prw(chromosome(&population_current)[Population_size], chromosome(&population_next_generation)[Population_size], chromosome &best_individual);
//交叉操作
void crossover(chromosome (&population_next_generation)[Population_size]);
//突变操作
void mutation(chromosome (&population_next_generation)[Population_size]);
/****************************************/

// 主函数
int main()
{
    /*****初始化定义的种群和个体*****/
    clock_t start, end;//开始计时,精确到秒
    start = clock();
    /****************************************/


    /*****初始化定义的种群和个体*****/
    chromosome population_current[Population_size];                    //当前种群
    chromosome population_next_generation[Population_size];       //产生的下一代的种群
    chromosome best_individual;                                                 //记录适应度的最大值
    chromosome zeros_chromosome;                                                //定义一个全为0的个体，用于群体中某个个体的重置
    /****************************************/

    int i = 0, k = 0,l = 0, m = 0;//循环变量

    //*****初始化定义的种群和个体*****
    //首先初始化zeros_chromosome，后使用之初始化其他个体
    for (i = 0; i < Chromosome_length; i++)
        zeros_chromosome.bit[i] = 0;
    zeros_chromosome.fitness = 0.0;
    zeros_chromosome.value = 0.0;
    zeros_chromosome.rate_fit = 0.0;
    zeros_chromosome.cumu_fit = 0.0;

    best_individual = zeros_chromosome;
    for (i = 0; i < Population_size; i++)
    {
        population_current[i] = zeros_chromosome;
        population_next_generation[i] = zeros_chromosome;
    }
    /****************************************/


    printf("\nWelcome to the Genetic Algorithm！\n");  //
    printf("The Algorithm is based on the function y = -x^2 + 5 to find the maximum value of the function.\n");

    printf("\nPlease enter the no. of iterations\n请输入您要设定的迭代数 : ");
    // 输入迭代次数，传送给参数 iteration_num
    scanf("%d", &iteration_num);


    //种群初始化，得到个体的二进制字符串
    population_initialize(population_current);
    //更新种群内个体的属性值
    fresh_property(population_current);
    // 开始迭代
    for (i = 0; i< iteration_num; i++)
    {
        // 输出当前迭代次数
        printf("\n当前种群第i = %d代\n", i+1);

        for (k = 0; k<Population_size; k++)
        {
            printf("individual[%2d]=", k);
            for (l = 0; l < Chromosome_length; l++)
                printf("%d", population_current[k].bit[l]);
            printf("        value=%10f    fitness = %f\n", population_current[k].value, population_current[k].fitness);
        }

        //挑选优秀个体组成新的种群
        seletc_prw(population_current,population_next_generation,best_individual);
        //对选择后的种群进行交叉操作
        crossover(population_next_generation);
        //对交叉后的种群进行变异操作
        mutation(population_next_generation);
        //更新种群内个体的属性值
        fresh_property(population_next_generation);
        //将population_next_generation的值赋给population_current，并清除population_next_generation的值
        for (m = 0; m < Population_size; m++)
        {
            population_current[m] = population_next_generation[m];
            population_next_generation[m] = zeros_chromosome;
        }
        //检验时间是否到90s
        end = clock();
        if (double(end - start) / CLK_TCK> 89)
            break;
    }
    //输出所用时间
    printf("\n 迭代%d次所用时间为： %f\n", iteration_num, double(end - start) / CLK_TCK);

    //输出结果
    printf("\n 当x = %f时 ,函数值最大为：%f \n", best_individual.value, best_individual.fitness);



    system("pause");

    return 0;
}


//函数：种群初始化
//输入是数组的引用
//调用时，只需输入数组名
void population_initialize(chromosome (&population_current)[Population_size])
{
    int i = 0, j = 0;

    //产生随机数种子
    srand((unsigned)time(NULL));
    //遍历种群中的每个染色体
    for (j = 0; j<Population_size; j++)
    {
        //随机初始化染色体的每一位
        for (i = 0; i<Chromosome_length; i++)
        {
            // 随机产生染色体上每一个基因位的值，0或1
            population_current[j].bit[i] = rand()% 2;
        }

    }

}


// 函数：将二进制换算为十进制
void decode(chromosome &population_current)
{//此处的染色体长度为，其中个表示符号位
    int i = 0;
    population_current.value = 0;
    //低位在前，高位再后
    for( i = 0 ; i < Chromosome_length -1; i++ )
        population_current.value += (double)pow(2, i) * (double)population_current.bit[i];    //遍历染色体二进制编码,
    //最高位为符号位，如果是1代表负数
    if (population_current.bit[Chromosome_length - 1] == 1)
        population_current.value = 0 - population_current.value;

}

//函数:计算适应度
double objective_function(double x)
{
    double y;
    // 目标函数：y= - ( (x-1)^ 2 ) +5
    y = -((x - 1) * (x - 1)) + 10;
    return(y);
}

//函数：更新种群内个体的属性值
//说明：当种群中个体的二进制串确定后，就可以计算每个个体fitness、value、rate_fit 、cumu_fit
//输入：
//chromosome (&population_current)[Population_size] 当前代种群的引用
void fresh_property(chromosome (&population_current)[Population_size])
{
    int j = 0;
    double sum = 0;

    for (j = 0; j < Population_size; j++)
    {

    //染色体解码，将二进制换算为十进制，得到一个整数值
        //计算二进制串对应的10进制数值
        decode(population_current[j]);
        //计算染色体的适应度
        population_current[j].fitness = objective_function(population_current[j].value);
        sum = sum + population_current[j].fitness;

    }


    //计算每条染色体的适应值百分比及累计适应度值的百分比，在轮盘赌选择法时用它选择染色体
    population_current[0].rate_fit = population_current[0].fitness / sum;
    population_current[0].cumu_fit = population_current[0].rate_fit;
    for (j = 1; j < Population_size; j++)
    {
        population_current[j].rate_fit = population_current[j].fitness / sum;
        population_current[j].cumu_fit = population_current[j].rate_fit + population_current[j-1].cumu_fit;
    }


}

//函数：基于轮盘赌选择方法，对种群中的染色体进行选择
//输入：
//chromosome (&population_current)[Population_size] 当前代种群的引用
//chromosome (&population_next_generation)[Population_size] 选择出的下一代种群的引用
//chromosome &best_individual 当前代种群中的最优个体
void seletc_prw(chromosome (&population_current)[Population_size],
                chromosome (&population_next_generation)[Population_size],
                chromosome &best_individual)
{

    int i = 0, j = 0;
    double rate_rand = 0.0;
    //best_individual = population_current[0];
    //产生随机数种子
    srand((unsigned)time(NULL));
    for (i = 0; i < Population_size; i++)
    {
        rate_rand = (float)rand() / (RAND_MAX);
        if (rate_rand < population_current[0].cumu_fit)
            population_next_generation[i] = population_current[0];
        else
        {
            for (j = 0; j < Population_size; j++)
            {
                if (population_current[j].cumu_fit <= rate_rand && rate_rand < population_current[j + 1].cumu_fit)
                {
                    population_next_generation[i] = population_current[j + 1];
                    break;
                }
            }
        }

        //如果当前个体比目前的最有个体还要优秀，则将当前个体设为最优个体
        if(population_current[i].fitness > best_individual.fitness)
            best_individual = population_current[i];
    }

}


// 函数：交叉操作
void crossover(chromosome (&population_next_generation)[Population_size])
{
    int i = 0,j = 0;
    double rate_rand = 0.0;
    short int bit_temp = 0;
    int num1_rand = 0, num2_rand = 0, position_rand = 0;
    //产生随机数种子
    srand((unsigned)time(NULL));
    //应当交叉变异多少次呢？先设定为种群数量
    for (j = 0; j<Population_size; j++)
    {
        rate_rand = (float)rand()/(RAND_MAX);
        //如果小于交叉概率就进行交叉操作
        if(rate_rand <= rate_crossover)
        {
            //随机产生两个染色体
            num1_rand = (int)rand()%(Population_size);
            num2_rand = (int)rand()%(Population_size);
            //随机产生两个染色体的交叉位置
            position_rand = (int)rand()%(Chromosome_length - 1);
            //采用单点交叉，交叉点之后的位数交换
            for (i = position_rand; i<Chromosome_length; i++)
            {
                bit_temp = population_next_generation[num1_rand].bit[i];
                population_next_generation[num1_rand].bit[i] = population_next_generation[num2_rand].bit[i];
                population_next_generation[num2_rand].bit[i] = bit_temp;
            }

        }
    }

}

// 函数：变异操作
void mutation(chromosome (&population_next_generation)[Population_size])
{
    int position_rand = 0;
    int i = 0;
    double rate_rand = 0.0;
    //产生随机数种子
    srand((unsigned)time(NULL));
    //变异次数设定为种群数量
    for (i = 0; i<Population_size; i++)
    {
        rate_rand = (float)rand()/(RAND_MAX);
        //如果大于交叉概率就进行变异操作
        if(rate_rand <= rate_mutation)
        {
            //随机产生突变位置
            position_rand = (int)rand()%(Chromosome_length);
            //突变
            if (population_next_generation[i].bit[position_rand] == 0)
                population_next_generation[i].bit[position_rand] = 1;
            else
                population_next_generation[i].bit[position_rand] = 0;

        }

    }
}

变邻域搜索算法求解TSP问题

////////////////////////
//TSP问题 变邻域搜索求解代码
//基于Berlin52例子求解
//作者：infinitor
//时间：2018-04-12
////////////////////////


#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <windows.h>
#include <memory.h>
#include <string.h>
#include <iomanip>

#define DEBUG

using namespace std;

#define CITY_SIZE 52 //城市数量


//城市坐标
typedef struct candidate
{
    int x;
    int y;
}city, CITIES;

//解决方案
typedef struct Solution
{
    int permutation[CITY_SIZE]; //城市排列
    int cost;						 //该排列对应的总路线长度
}SOLUTION;

//城市排列
int permutation[CITY_SIZE];
//城市坐标数组
CITIES cities[CITY_SIZE];


//berlin52城市坐标，最优解7542好像
CITIES berlin52[CITY_SIZE] =
{
{ 565,575 },{ 25,185 },{ 345,750 },{ 945,685 },{ 845,655 },
{ 880,660 },{ 25,230 },{ 525,1000 },{ 580,1175 },{ 650,1130 },{ 1605,620 },
{ 1220,580 },{ 1465,200 },{ 1530,5 },{ 845,680 },{ 725,370 },{ 145,665 },
{ 415,635 },{ 510,875 },{ 560,365 },{ 300,465 },{ 520,585 },{ 480,415 },
{ 835,625 },{ 975,580 },{ 1215,245 },{ 1320,315 },{ 1250,400 },{ 660,180 },
{ 410,250 },{ 420,555 },{ 575,665 },{ 1150,1160 },{ 700,580 },{ 685,595 },
{ 685,610 },{ 770,610 },{ 795,645 },{ 720,635 },{ 760,650 },{ 475,960 },
{ 95,260 },{ 875,920 },{ 700,500 },{ 555,815 },{ 830,485 },{ 1170,65 },
{ 830,610 },{ 605,625 },{ 595,360 },{ 1340,725 },{ 1740,245 }
};


//随机数产生函数，利用系统时间，精确到微妙，再加一个变量i组合产生随机数。
//单单用srand(time(NULL)) + rand()达不到效果，因为函数执行太快。时间间隔太短
int randEx(int i)
{
    LARGE_INTEGER seed;
    QueryPerformanceFrequency(&seed);
    QueryPerformanceCounter(&seed);
    srand((unsigned int)seed.QuadPart + i);

    return rand();
}


//计算两个城市间距离
int distance_2city(city c1, city c2)
{
    int distance = 0;
    distance = sqrt((double)((c1.x - c2.x)*(c1.x - c2.x) + (c1.y - c2.y)*(c1.y - c2.y)));

    return distance;
}

//根据产生的城市序列，计算旅游总距离
//所谓城市序列，就是城市先后访问的顺序，比如可以先访问ABC，也可以先访问BAC等等
//访问顺序不同，那么总路线长度也是不同的
//p_perm 城市序列参数
int cost_total(int * cities_permutation, CITIES * cities)
{
    int total_distance = 0;
    int c1, c2;
    //逛一圈，看看最后的总距离是多少
    for (int i = 0; i < CITY_SIZE; i++)
    {
        c1 = cities_permutation[i];
        if (i == CITY_SIZE - 1) //最后一个城市和第一个城市计算距离
        {
            c2 = cities_permutation[0];
        }
        else
        {
            c2 = cities_permutation[i + 1];
        }
        total_distance += distance_2city(cities[c1], cities[c2]);
    }

    return total_distance;
}

//获取随机城市排列
void random_permutation(int * cities_permutation)
{
    int i, r, temp;
    for (i = 0; i < CITY_SIZE; i++)
    {
        cities_permutation[i] = i; //初始化城市排列，初始按顺序排
    }


    for (i = 0; i < CITY_SIZE; i++)
    {
        //城市排列顺序随机打乱
        srand((unsigned int)time(NULL));
        int j = rand();
        r = randEx(++j) % (CITY_SIZE - i) + i;
        temp = cities_permutation[i];
        cities_permutation[i] = cities_permutation[r];
        cities_permutation[r] = temp;
    }
}


//颠倒数组中下标begin到end的元素位置
void swap_element(int *p, int begin, int end)
{
    int temp;
    while (begin < end)
    {
        temp = p[begin];
        p[begin] = p[end];
        p[end] = temp;
        begin++;
        end--;
    }
}


//邻域结构0 利用swap_element算子搜索
void neighborhood_zero(SOLUTION & solution, CITIES * cities)
{
    SOLUTION current_solution = solution;

    int count = 0;
    int max_no_improve = 10;

    do
    {
        count++;
        for (int i = 0; i < CITY_SIZE - 1; i++)
        {
            for (int k = i + 1; k < CITY_SIZE; k++)
            {
                current_solution = solution;
                swap_element(current_solution.permutation, i, k);

                current_solution.cost = cost_total(current_solution.permutation, cities);
                if (current_solution.cost < solution.cost)
                {
                    solution = current_solution;
                    count = 0; //count复位
                }

            }
         }

    } while (count <= max_no_improve);



}




// two_opt_swap算子
void two_opt_swap(int *cities_permutation, int b, int c)
{
    vector<int> v;
    for (int i = 0; i < b; i++)
    {
        v.push_back(cities_permutation[i]);
    }
    for (int i = c; i >= b; i--)
    {
        v.push_back(cities_permutation[i]);
    }
    for (int i = c + 1; i < CITY_SIZE; i++)
    {
        v.push_back(cities_permutation[i]);
    }

    for (int i = 0; i < CITY_SIZE; i++)
    {
        cities_permutation[i] = v[i];
    }

}

//邻域结构1 使用two_opt_swap算子
void neighborhood_one(SOLUTION & solution, CITIES *cities)
{
    int i, k, count = 0;
    int max_no_improve = 10;
    SOLUTION current_solution = solution;
    do
    {
        count++;
        for (i = 0; i < CITY_SIZE - 1; i++)
        {
            for (k = i + 1; k < CITY_SIZE; k++)
            {
                current_solution = solution;
                two_opt_swap(current_solution.permutation, i, k);

                current_solution.cost = cost_total(current_solution.permutation, cities);
                if (current_solution.cost < solution.cost)
                {
                    solution = current_solution;

                    count = 0; //count复位
                }

             }
          }
    }while (count <= max_no_improve);

}
//two_h_opt_swap算子
void two_h_opt_swap(int *cities_permutation, int a, int d)
{
    int n = CITY_SIZE;
    vector<int> v;
    v.push_back(cities_permutation[a]);
    v.push_back(cities_permutation[d]);
    // i = 1 to account for a already added
    for (int i = 1; i < n; i++)
    {
        int idx = (a + i) % n;
        // Ignore d which has been added already
        if (idx != d)
        {
            v.push_back(cities_permutation[idx]);
        }
    }

    for (int i = 0; i < v.size(); i++)
    {
        cities_permutation[i] = v[i];
    }

}


//邻域结构2 使用two_h_opt_swap算子
void neighborhood_two(SOLUTION & solution, CITIES *cities)
{
    int i, k, count = 0;
    int max_no_improve = 10;
    SOLUTION current_solution = solution;
    do
    {
        count++;
        for (i = 0; i < CITY_SIZE - 1; i++)
        {
            for (k = i + 1; k < CITY_SIZE; k++)
            {
                current_solution = solution;
                two_h_opt_swap(current_solution.permutation, i, k);

                current_solution.cost = cost_total(current_solution.permutation, cities);

                if (current_solution.cost < solution.cost)
                {
                    solution = current_solution;
                    count = 0; //count复位
                }

            }
        }
    } while (count <= max_no_improve);
}


//VND
//best_solution最优解
//current_solution当前解
void variable_neighborhood_descent(SOLUTION & solution, CITIES * cities)
{

    SOLUTION current_solution = solution;
    int l = 0;
    cout  <<"=====================VariableNeighborhoodDescent=====================" << endl;
    while(true)
    {
        switch (l)
        {
        case 0:
            neighborhood_zero(current_solution, cities);
            cout << setw(45) << setiosflags(ios::left) << "Now in neighborhood_zero, current_solution = " << current_solution.cost << setw(10) << setiosflags(ios::left) << "  solution = " << solution.cost << endl;
            if (current_solution.cost < solution.cost)
            {
                solution = current_solution;
                l = -1;
            }
            break;
        case 1:
            neighborhood_one(current_solution, cities);
            cout << setw(45) << setiosflags(ios::left)  <<"Now in neighborhood_one , current_solution = " << current_solution.cost << setw(10) << setiosflags(ios::left) << "  solution = " << solution.cost << endl;
            if (current_solution.cost < solution.cost)
            {
                solution = current_solution;
                l = -1;
            }
            break;
        case 2:
            neighborhood_two(current_solution, cities);
            cout << setw(45) << setiosflags(ios::left) << "Now in neighborhood_two , current_solution = " << current_solution.cost << setw(10) << setiosflags(ios::left) << "  solution = " << solution.cost << endl;
            if (current_solution.cost < solution.cost)
            {
                solution = current_solution;
                l = -1;
            }
            break;

        default:
            return;
        }
        l++;

    }

}

//将城市序列分成4块，然后按块重新打乱顺序。
//用于扰动函数
void double_bridge_move(int * cities_permutation)
{
    srand((unsigned int)time(NULL));
    int j = rand();
    int pos1 = 1 + randEx(++j) % (CITY_SIZE / 4);
    int pos2 = pos1 + 1 + randEx(++j) % (CITY_SIZE / 4);
    int pos3 = pos2 + 1 + randEx(++j) % (CITY_SIZE / 4);

    int i;
    vector<int> v;
    //第一块
    for (i = 0; i < pos1; i++)
    {
        v.push_back(cities_permutation[i]);
    }

    //第二块
    for (i = pos3; i < CITY_SIZE; i++)
    {
        v.push_back(cities_permutation[i]);
    }
    //第三块
    for (i = pos2; i < pos3; i++)
    {
        v.push_back(cities_permutation[i]);
    }

    //第四块
    for (i = pos1; i < pos2; i++)
    {
        v.push_back(cities_permutation[i]);
    }


    for (i = 0; i < (int)v.size(); i++)
    {
        cities_permutation[i] = v[i];
    }


}

//抖动
void shaking(SOLUTION &solution, CITIES *cities)
{
    double_bridge_move(solution.permutation);
    solution.cost = cost_total(solution.permutation, cities);
}


void variable_neighborhood_search(SOLUTION & best_solution, CITIES * cities)
{

    int max_iterations = 5;

    int count = 0, it = 0;

    SOLUTION current_solution = best_solution;

    //算法开始
    do
    {
        cout << endl << "\t\tAlgorithm VNS iterated  " << it << "  times" << endl;
        count++;
        it++;
        shaking(current_solution, cities);

        variable_neighborhood_descent(current_solution, cities);

        if (current_solution.cost < best_solution.cost)
        {
            best_solution = current_solution;
            count = 0;
        }

        cout << "\t\t全局best_solution = " << best_solution.cost << endl;

    } while (count <= max_iterations);


}


int main()
{

    SOLUTION best_solution;

    random_permutation(best_solution.permutation);
    best_solution.cost = cost_total(best_solution.permutation, berlin52);

    cout << "初始总路线长度 = " << best_solution.cost << endl;

    variable_neighborhood_search(best_solution, berlin52);

    cout << endl << endl << "搜索完成！ 最优路线总长度 = " << best_solution.cost << endl;
    cout << "最优访问城市序列如下：" << endl;
    for (int i = 0; i < CITY_SIZE; i++)
    {
        cout << setw(4) << setiosflags(ios::left) << best_solution.permutation[i];
    }

    cout << endl << endl;

    return 0;
}