当前位置:首页 » 操作系统 » 算法实验六

算法实验六

发布时间: 2023-07-10 13:42:19

A. 算法与数据结构实验顺序表的应用实验报告

者visual c++都行。
看看这个也许你会明白的更多一些。
实验一 多项式相加

一、实验目的
熟悉链表的使用。
掌握如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。

二、实验要求
熟悉C语言编程

三、实验内容
对于两个一元多项式中所有指数相同的项,对应系数相加,若其和不为零,则构成“和多项式”的一项;对于两个一元多项式中所有指数不相同的项,则分别复抄到“和多项式”中去。

四、实验步骤
1. 用链表作一元多项式的数据结构,用C语言对链表作说明
2. 生成输入一元多项式的函数
3. 输入一元多项式A(x)和B(x)
4. 以一元多项式A(x)为和多项式,将B(x)多项式中系数加入到A(x)中去

实验二 后缀表达式计算

一、实验目的
熟悉栈的使用。
掌握如何使用C语言实现栈的说明、创建以及进栈和出栈等操作。

二、实验要求
熟悉C语言编程。

三、实验内容
先将中缀表达式(就是我们通常所见的)转换为后缀表达式,比如 a+b*c+d 要变成 abc*+d+;转换的方法用栈来实现,涉及到运算符的优先级;然后用另一个栈来对后缀表达式计算结果

四、实验步骤
1.读入字母/数字--〉字母/数字进栈
2.读入运算符--〉退出两个字母/数字,用运算符计算结果,并将结果进栈
3.栈能刚好退完,则最后的即为结果。否则表明表达式有误

实验三 Kmp算法

一、实验目的
熟悉字符串的使用。
掌握如何kmp算法实验字符串的模式匹配。

二、实验要求
熟悉C语言编程。

三、实验内容
求出子串(模式串)的next,利用kmp算法实验模式与主串的匹配算法。

四、实验步骤
1.生成模式串的next函数
2.从第1个字符开始,进行模式串与主串的比较,
3.如果出现失配,将模式串的第next[j]位置开始,继续与主串进行比较。

实验四 Huffman 编码

一、实验目的
熟悉Huffman编码方法。
了解并弄懂Huffman编码实现信息的无损压缩原理。

二、实验要求
熟悉C语言编程。

三、实验内容
1.根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F=,其中每棵二叉树Ti中只有一个带树为Ti的根结点
2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置其根结点的权值为其左右子树权值之和
3.在F中删除这两棵树,同时将新得到的二叉树加入F中
4.重复2, 3,直到F只含一棵树为止

四、实验步骤
1.用C语言实现二叉树的说明
2.输入n个权值,并生成n个二叉树
3.对n个二叉树逐步生成Huffman树
4.对Huffman树的每个叶子结点生成编码

实验五 关键路径

一、实验目的
熟悉关键路径的实现方法。
了解AOE-网以及关键路径在工程实践中的应用。

二、实验要求
熟悉C语言编程。

三、实验内容
根据输入的弧,生成AOE-网。从始点开始,找出到终点的多条路径,求这些路径上的关键活动。由关键活动组成的从始点到终点的路径,即为关键路径。

四、实验步骤
1.输入e条弧,生成AOE-网的存储结构。
2.从始点v0出发,令ve[0]=0,按拓扑有序求ve[j]
3.从终点vn-1出发,令vl[n-1]=ve[n-1],按逆拓扑有序求vl[i]
4.根据各顶点的ve和vl值,求每条弧(活动)ai的最早开始时间e[ai]和最迟开始时间l[ai]
5.如果e[ai]=l[ai],则ai为关键活动

实验六 最短路经

一、实验目的
熟悉最短路径的实现方法。
了解AOE-网以及最短路径在求解实际问题中的应用。

二、实验要求
熟悉C语言编程。

三、实验内容
从始点v0开始,逐步求v0到其它可达的各顶点的最短路径,直到所有顶点计算完成为止。

四、实验步骤
1.输入e条弧,生成AOE-网的存储结构。
2.初始化: S ← ;
dist[j] ← Edge[0][j], j = 1, 2, …, n-1; // n为图中顶点个数
3.求出最短路径的长度:
dist[k] ← min , i  V- S ;
S ← S U ;
4.修改从v0到V-S集合中各顶点的最短路径:
dist[i] ← min,
对于每一个 i 属于 V- S ;
5.判断:若 S = V, 则算法结束,否则转 2。

实验七 二叉排序树

一、实验目的
熟悉二叉排序树的使用。
掌握如何使用C语言实现二叉树的说明、创建以及二叉排序树的生成等操作。

二、实验要求
熟悉C语言编程。

三、实验内容
给定一个记录关键字的值,与二叉排序树的根结点值比较,如果小于根结点的值,则向左子树查找;如果大于根结点的值,则向右子树查找。如果查找到叶子结点leaf,仍没有找到记录,则:如果关键字的值小于leaf的值,则插入该leaf结点的左边,做leaf的左孩子,否则做leaf的右孩子。

四、实验步骤
1.用C语言实现二叉树的说明
2.直接将输入的值作为根结点的值
3.与根结点比较,小于则放到左子树上,大于则放到右子树上。

实验八 希尔排序

一、实验目的
熟悉希尔排序的使用。
掌握如何使用C语言实现若干记录的排序。

二、实验要求
熟悉C语言编程。

三、实验内容
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

四、实验步骤
1.输入待排序记录
2.首先取一个整数 gap < n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中
3.在每一个子序列中分别施行直接插入排序。
4.然后缩小间隔 gap, 例如取 gap = gap/2
5.重复上述的子序列划分和排序工作,直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。

实验九 快速排序

一、实验目的
熟悉快速排序的使用。
掌握如何使用C语言实现若干记录的排序。

二、实验要求
熟悉C语言编程。

三、实验内容
通过一趟将待排记录分割成独立的两个部分,其中一部分记录的关键字均比另一部分记录的关键字小。再对两个部分分别进行快速排序。

四、实验步骤
1.输入待排序的记录,并选择第一个记录作为pivotkey记录
2.从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+1
3.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-1
4.重复2,3,直到low=high,将枢轴记录放在low(high)指向的位置
5.重复2,3,4,直到整个记录有序为止

实验十 堆排序

一、实验目的
熟悉堆排序的使用。
掌握如何使用C语言实现若干记录的排序。

二、实验要求
熟悉C语言编程。

三、实验内容
首先将一个无序序列建成一个堆;然后输出堆顶元素;在输出堆顶元素之后,调整剩余的元素成为一个新堆。

四、实验步骤
1.输入记录,按顺序创建一个完全二叉树
2.根据筛选算法,从最后一个结点开始,一直到根结点,逐步筛选,建造初始堆。
3.输出堆顶记录,将最后一个结点放到堆顶,并做筛选,重新建造一个堆
4.直到所有记录输出为止

B. 页面置换算法的实验

#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*进程名称的最大长度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默认内存的大小*/
#define DEFAULT_MEM_START 0 /*默认内存的起始位置*/

/* 内存分配算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*内存大小*/
int ma_algorithm = MA_FF; /*当前分配算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*设置内存大小标志*/

struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;

struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;

/*初始化空闲块,默认为一块,可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{

struct free_block_type *fb;

fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}

void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}

/*设置内存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重复设置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能够放下将要存放数据的块,First-first使用第一个能够放下将要存放数据的块,Worst-fit使用最大的能够放下将要存放数据的块。*/
/* 设置当前的分配算法 */
/*分区分配算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次适应算法(FF):。 */
printf("\t2 - Best Fit\n");/*最佳适应算法(BF): */

printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定算法重新排列空闲区链表*/
rearrange(ma_algorithm);
}

void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}

void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址递增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF算法重新整理内存空闲块链表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}

}

*/
/*按WF算法重新整理内存空闲块链表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}
}
*/

/*按指定的算法整理内存空闲块链表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}

/*创建新的进程,主要是获取内存的申请数量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;

printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 从空闲区分配内存,ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值,则赋值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功,将该已分配块的描述插入已分配链表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}

/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配后空闲空间足够大,则分割*/

else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割后空闲区成为小碎片,一起分配*/

return 1;
}
}
pre = fbt;
fbt = fbt->next;
}

return -1;
}

/*将ab所表示的已分配区归还,并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;

fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果当前空闲区与后面的空闲区相连,则合并*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按当前的算法排列空闲区*/
return 1;
}

/*?释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;

if(free_ab == allocated_block_head)
{ /*如果要释放第一个节点*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;

while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要删除的进程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}

/*删除进程,归还分配的存储空间,并删除描述该进程内存分配的节点*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*释放ab所表示的分配区*/
dispose(ab); /*释放ab数据结构节点*/

}
}

/* 显示当前内存的使用情况,包括空闲区的情况和已经分配的情况 */

int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");

/* 显示空闲区 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 显示已分配区 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}

**********************************************************************
楼主啊,小女子给你的是残缺版滴,要是你给我分,我就把剩下滴给你,上次在北京大学贴吧都被人骗了,世道炎凉啊O(∩_∩)O~

C. 优化算法笔记(六)遗传算法

遗传算法(Genetic Algorithms,GA)是一种粗衡模拟自然中生物的遗传、进化以适应环境的智能算法。由于其算法流程简单,参数较少优化速度较快,效果较好,在图像处理、函数优化、信号处理、模式识别等领域有着广泛的应用。
在遗传算法(GA)中,每一个待求问题的候选解被抽象成为种群中一个个体的基因。种群中个体基因的好坏由表示个体基因的候选解在待求问题中的所的得值来评判。种群中的个体通过与其他个体交叉产生下一代,每一代中个体均只进行一次交叉。两个进行交叉的个体有一定几率交换一个或者多个对应位的基因来产生新的后代。每个后代都有一定的概率发生变异。发生变异的个体的某一位或某几位基因会变异成其他值。最终将以个体的适应度值为概率选取个体保留至下一代。

遗传算法启发于生物的繁殖与dna的重组,本次的主角选什么呢?还是根据大家熟悉的孟德尔遗传规律选豌豆吧,选动物的话又会有人疑车,还是植物比较好,本次的主角就是它了。

遗传算法包含三个操作(算子):交叉,变异和选择操作。下面我们将详细介绍这三个操作。
大多数生物的遗传信息都储存在DNA,一种双螺旋结构的复杂有机化合物。其含氮碱基为腺嘌呤、鸟嘌呤、胞嘧啶及胸腺嘧啶。

表格中表示了一个有10个基因的个体,它们每一个基因的值为0或者1。

生物的有性生殖一般伴随着基因的重组。遗传算法中父辈和母辈个体产生子代个体的过程称为交叉。

表中给出了两个豌豆的基因,它们均有10个等位基因(即编号相同的基因)。
遗传算法的交叉过程会在两个个体中随机选择1位或者n位基因进行交叉,即这两个个体交换等位基因。
如,A豌豆和B豌豆在第6位基因上进行交叉,则其结果如下

当两个个体交叉的等位基因相同时,交叉过程也有可能没有产生新慧衡的个体,如交叉A豌豆和B豌豆的第2位基因时,交叉操作并没有产生新的基因。

一般的会给群体设定一个交叉率,crossRate,表示会在群体中选取一定比例的个体进行交叉,交叉率相对较大,一般取值为0.8。

基因的变异是生物进化的一个主要因素。
遗传算法中变异操作相对简单,只需要将一个随机位基因的值修改就行了,因为其值只为0或1,那么当基因为0时,变异操作会将其值设为1,当基因值为1时,变异操作会将其值设为0。

上图表示了A豌豆第3位基因变异后的基因编码。
与交叉率相似,变异操作也有变异率,alterRate,但是变异率会远低于交叉率,否则会产生大量的随机基因。一般变异率为0.05。

选择操作是遗传算法中的一个关键操作,它的主要作用就是根据一定的策略随机选择个体保留至下一代。适应度越优的岩碧做个体被保留至下一代的概率越大。
实现上,我们经常使用“轮盘赌”来随机选择保留下哪个个体。

假设有4个豌豆A、B、C、D,它们的适应度值如下:

适应度值越大越好,则它们组成的轮盘如下图:

但由于轮盘赌选择是一个随机选择过程,A、B、C、D进行轮盘赌选择后产生的下一代也有可能出现A、A、A、A的情况,即虽然有些个体的适应度值不好,但是运气不错,也被选择留到了下一代。
遗产算法的三个主要操作介绍完了,下面我们来看看遗传算法的总体流程:

前面我们说了遗传算法的流程及各个操作,那么对于实际的问题我们应该如何将其编码为基因呢?

对于计算机来所所有的数据都使用二进制数据进行存放,如float类型和double类型的数据。
float类型的数据将保存为32位的二进制数据:1bit(符号位) 8bits(指数位) 23bits(尾数位)
如-1.234567f,表示为二进制位

Double类型的数据将保存为64位的二进制数据:1bit(符号位) 11bits(指数位) 53bits(尾数位)
如-1.234567d,表示为二进制为

可以看出同样的数值不同的精度在计算机中存储的内容也不相同。之前的适应度函数 ,由于有两个double类型的参数,故其进行遗传算法基因编码时,将有128位基因。
虽然基因数较多,但好在每个基因都是0或者1,交叉及变异操作非常简单。

相比二进制编码,十进制编码的基因长度更短,适应度函数 有两个输入参数,那么一个个体就有2个基因,但其交叉、变异操作相对复杂。
交叉操作
方案1:将一个基因作为一个整体,交换两个个体的等位基因。
交换前

交换第1位基因后

方案2:将两个个体的等位基因作为一个整体,使其和不变,但是值随机
交换前

交换第1位基因后

假设A、B豌豆的第一位基因的和为40,即 ,第一位基因的取值范围为0-30,那么A、B豌豆的第一位基因的取值范围为[10,30],即 为[0,30]的随机数, 。
变异操作,将随机的一位基因设置为该基因取值范围内的随机数即可。

这个过程说起来简单但其实现并不容易。

我们要将它们的值映射到一个轴上才能进行随机选择,毕竟我们无法去绘制一个轮盘来模拟这个过程

如图,将ABCD根据其值按顺序排列,取[0,10]内的随机数r,若r在[0,1]内则选择A,在(1,3]内则选择B,在(3,6]内则选择C,在(6,10]则选择D。
当然这仍然会有问题,即当D>>A、B、C时,假如它们的值分布如下

那么显然,选D的概率明显大于其他,根据轮盘赌的选择,下一代极有可能全是D的后代有没有办法均衡一下呢?
首先我想到了一个函数,

不要问我为什么我不知道什么是神经什么网络的,什么softmax、cnn统统没听说过。

这样一来,它们之间的差距没有之前那么大了,只要个体适应度值在均值以上那么它被保留至下一代的概率会相对较大,当然这样缩小了个体之间的差距,对真正优秀的个体来说不太公平,相对应,我们可以在每次选择过程中保留当前的最优个体到下一代,不用参与轮盘赌这个残酷的淘汰过程。

最令人高兴的环节到了,又可以愉快的凑字数了。

由于遗传算法的收敛速度实在是太慢,区区50代,几乎得不到好的结果,so我们把它的最大迭代次数放宽到200代。

使用二进制编码来进行求解
参数如下:

求解过程如上图,可以看出基因收敛的很快,在接近20代时就图中就只剩一个点了,之后的点大概是根据变异操作产生。看一下最后的结果。

可以看出最好的结果已经得到了最优解,但是10次实验的最差值和平均值都差的令人发指。为什么会这样呢?

问题出在二进制编码上,由于double类型的编码有11位指数位和52位小数位,这会导致交叉、变异操作选到指数位和小数位的概率不均衡,在小数位上的修改对结果的影响太小而对指数为的修改对结果的影响太大,
如-1.234567d,表示为二进制为

对指数为第5位进行变异操作后的结果为-2.8744502924382686E-10,而对小数位第5为进行变异操作后的结果为-1.218942。可以看出这两部分对数值结果的影响太不均衡,得出较好的结果时大概率是指数位与解非常相近,否则很难得出好的结果,就像上面的最差值和均值一样。
所以使用上面的二进制编码不是一个好的基因编码方式,因此在下面的实验中,将使用十进制来进行试验。

使用:十进制编码来进行求解
参数如下:

我们可以看到直到40代时,所有的个体才收束到一点,但随后仍不断的新的个体出现。我们发现再后面的新粒子总是在同一水平线或者竖直线上,因为交叉操作直接交换了两个个体的基因,那么他们会相互交换x坐标或者y坐标,导致新个体看起来像在一条直线上。
我们来看看这次的结果。

这次最优值没有得到最优解,但是最差值没有二进制那么差,虽然也不容乐观。使用交换基因的方式来进行交叉操作的搜索能力不足,加之轮盘赌的选择会有很大概率选择最优个体,个体总出现在矩形的边上。
下面我们先改变轮盘赌的选择策略,使用上面的sigmod函数方案,并且保留最优个体至下一代。

使用:十进制编码来进行求解
参数如下:

看图好像跟之前的没什么区别,让我们们看看最终的结果:

可以看出,最优值没有什么变化,但是最差值和平均值有了较大的提升,说明该轮盘赌方案使算法的鲁棒性有了较大的提升。在每次保留最优个体的情况下,对于其他的个体的选择概率相对平均,sigmod函数使得即使适应度函数值相差不太大的个体被选到的概率相近,增加了基因的多样性。

使用:十进制编码来进行求解,改变交叉方案,保持两个个体等位基因和不变的情况下随机赋值。
参数如下:

上图可以看出该方案与之前有明显的不同,在整个过程中,个体始终遍布整个搜索空间,虽然新产生的个体大多还是集中在一个十字架型的位置上,但其他位置的个体比之前的方案要多。
看看结果,

这次的结果明显好于之前的所有方案,但仍可以看出,十进制的遗传算法的精度不高,只能找到最优解的附近,也有可能是算法的收敛速度实在太慢,还没有收敛到最优解。

遗传算法的探究到此也告一段落,在研究遗传算法时总有一种力不从心的感觉,问题可能在于遗传算法只提出了一个大致的核心思想,其他的实现细节都需要自己去思考,而每个人的思维都不一样,一万个人能写出一万种遗传算法,其实不仅是遗传算法,后面的很多算法都是如此。
为什么没有对遗传算法的参数进行调优,因为遗传算法的参数过于简单,对结果的影响的可解释性较强,意义明显,实验的意义不大。

遗传算法由于是模仿了生物的进化过程,因此我感觉它的求解速度非常的慢,而且进化出来的结果不一定是最适应环境的,就像人的阑尾、视网膜结构等,虽然不是最佳的选择但是也被保留到了今天。生物的进化的随机性较大,要不是恐龙的灭绝,也不会有人类的统治,要不是人类有两只手,每只手有5根手指,也不会产生10进制。
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记(五)粒子群算法(3)
下一篇 优化算法笔记(七)差分进化算法

优化算法matlab实现(六)遗传算法matlab实现

热点内容
上传mp3外链 发布:2025-03-17 22:11:06 浏览:798
c语言写音乐 发布:2025-03-17 22:10:55 浏览:914
c语言位或和或 发布:2025-03-17 21:53:56 浏览:915
淘宝图片上传格式 发布:2025-03-17 21:48:55 浏览:941
博雅干细胞存储 发布:2025-03-17 21:24:07 浏览:53
dota2卡尔脚本 发布:2025-03-17 21:11:27 浏览:71
应用市场网站源码 发布:2025-03-17 21:09:46 浏览:413
linux怎么挂载 发布:2025-03-17 21:08:23 浏览:897
疫情数据库 发布:2025-03-17 20:58:00 浏览:670
excel怎么破解密码 发布:2025-03-17 20:49:32 浏览:360