遗传算法入门(连载之五)

2024-06-10 14:08

本文主要是介绍遗传算法入门(连载之五),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

   最近在学习有关遗传算法和神经网络方面的知识,网上查看了很多这方面的秘笈,只怪小生天生愚钝、才疏学浅,不能很好的领悟秘笈中的真谛,往往被弄得晕头转向、不知所措快哭了委屈。直到有一天无意中看到了博主zzwu写的有关这方面的文章,初读之,如温旧习;渐深入,觉甚好;遂一气呵成,犹如拨云见日、茅塞顿开。余甚怕在茫茫Internet中再无机会拜读之,遂收藏于此,以便众人观之,绝无其他不良用途。在此对博主再次深表感谢。

博文转自:http://blog.csdn.net/zzwu/article/details/561622


.

.
(连载之五)
.
扎自<游戏编程中的人工智能技术>第三章

 清华大学出版社

(本章由zzwu译)

3.4 帮助 Bob 回家( Helping Bob Home )

        由于寻找路径问题被看成是游戏人工智能的一块神圣基石,我们下面就来创建一个遗传算法,用在一个非常简单的场景中解决寻找路径问题。为此,我们将创建一个迷宫,它的左边有一入口,右边有一出口,并有一些障碍物散布在其中。然后在出发点放置一个虚拟的人,我们叫他鲍勃(Bob),然后要为他解决如何寻找路径的问题,使他能找到出口,并避免与所有障碍物相碰撞。下面我将说明怎样来产生Bob的染色体的编码,但首先需要解释怎样来表示迷宫...

   迷宫是一个2D整数型数组;用0来表示开放的空间,1代表墙壁或障碍物,5是起始点,8是出口。因此,整数数组:

.{ 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,
..5,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,8,
..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 }

   在屏幕上看起来将会有下面图3.5的样子:


图 3.5 Bob的迷宫,用红色标出了入口和出口

  作者已把这种地图设计方法封装在一个被称作CBobsMap的类中,它定义为:

 class CBobsMap
{           
      
private:
                
   //保存地图用的存储器 (一个2维整型数组)
    static const int map[MAP_HEIGHT][MAP_WIDTH];  
    static const int m_iMapWidth;   //地图的宽度   
    static const int m_iMapHeight;  //地图的高度 
    
   //起始点在数组中的下标        
    static const int m_iStartX;    
    static const int m_iStartY;              
       
   //终点的数组下标       
    static const int m_iEndX;              
    static const int m_iEndY;           

public:              
   //你可以利用这一数组作为 Bob 存储器,如果需要的话 
    int memory[MAP_HEIGHT][MAP_WIDTH];   
   
    CBobsMap() 
    { 
      ResetMemory(); 
    }
             
   //利用一个字符串来记录Bob行进的方向,其中每一个字符代表
   //Bob所走的一步;检查Bob离开出口还有多远; 
   //返回一个与到达出口距离成正比的适应性分数 
    double TestRoute(const vector &vecPath,
                     CBobsMap     &memory);             
                             
   //Render函数利用Windows GDI在一个给定的surface上显示地图
    void Render(const int    cxClient,
                const int    cyClient,
                HDC          surface); 

   //画出能够存放于存储器中的不管什么样的路径 
    void MemoryRender(const int cxClient,
                      const int cyClient.
                      HDC       surface); 
    void ResetMemory(); 
};

.     由上可以看出,我们只需要以常量的形式来保存地图数组以及起点和终点的坐标就行了。这些数据是在文件CBobsMap.cpp 中定义的,在光盘上你能找到它的相关的文件夹。除了存储迷宫的数据外,这个Map类也用来记录Bob在迷宫中所走过的路程:memory[][] 。这对遗传算法本身而言不是本质的,但为了显示目的,使你能看到 Bob 怎样在迷宫中漫游,设置一个记录是必需的。这里重要的是成员函数TestRoute(),它需要利用一系列的行进方向来检测Bob 走了多远。这里我不准备花费时间来列出TestRoute 函数的清单,因为这是十分简单的那种函数,但要列出来却可能需要长长的2页。我们只需要说明一下就行了。给出一个方向向量,它的每个分量能代表向北(North)、向南(South)、向东(East)、向西(West)四个方向之一,让Bob 按照它在地图中行走, TestRoute 计算 Bob 能到达的最远点的位置,然后返回一个适应性分数,它正比于Bob 最终位置离出口的距离。他所到达的位置离开出口愈近,奖励给他的适应性分数也愈高。如果他实际已到达了出口,则我们就要向他表示祝贺了,他将得到满分1。这时循环就会自动结束,因为你已经找到一个解了,可以喊乌拉了!
...再有,不要因为理解不了这个类的任何一点而操心。我们下面马上就会开始讨论有关的每一件事情的。

-连载5完-

这篇关于遗传算法入门(连载之五)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1048375

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

Java 创建图形用户界面(GUI)入门指南(Swing库 JFrame 类)概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包,是 JAVA 基础类的一部分,基于 Java AWT 构建,提供了一系列轻量级、可定制的图形用户界面(GUI)组件。 与 AWT 相比,Swing 提供了许多比 AWT 更好的屏幕显示元素,更加灵活和可定制,具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

MySQL-CRUD入门1

文章目录 认识配置文件client节点mysql节点mysqld节点 数据的添加(Create)添加一行数据添加多行数据两种添加数据的效率对比 数据的查询(Retrieve)全列查询指定列查询查询中带有表达式关于字面量关于as重命名 临时表引入distinct去重order by 排序关于NULL 认识配置文件 在我们的MySQL服务安装好了之后, 会有一个配置文件, 也就

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

MySQL入门到精通

一、创建数据库 CREATE DATABASE 数据库名称; 如果数据库存在,则会提示报错。 二、选择数据库 USE 数据库名称; 三、创建数据表 CREATE TABLE 数据表名称; 四、MySQL数据类型 MySQL支持多种类型,大致可以分为三类:数值、日期/时间和字符串类型 4.1 数值类型 数值类型 类型大小用途INT4Bytes整数值FLOAT4By

【QT】基础入门学习

文章目录 浅析Qt应用程序的主函数使用qDebug()函数常用快捷键Qt 编码风格信号槽连接模型实现方案 信号和槽的工作机制Qt对象树机制 浅析Qt应用程序的主函数 #include "mywindow.h"#include <QApplication>// 程序的入口int main(int argc, char *argv[]){// argc是命令行参数个数,argv是