简化的赛车游戏
经过简化的赛车游戏设定如下:一个有难度的最优解问题1、赛道如下图所示:
假设每个格子是1平方米
2、起点、终点:
起点如上图红点所示,位于左上角正方格上边的中点;终点是一条线段,位于左下角,如上图的红线所示。
3、行车规则:
(1)赛车被简化成了一个点
(2)赛道没有墙,赛车在到达终点前,一旦驶出灰色区域(驶入白色区域),即为挑战失败,成绩(用时)记为无穷大
(3)赛车的初速为0,可以以任意速度到达终点,即使到达终点后驶出灰色区域,成绩依然有效
(4)任何时候,赛车的加速度大小都不能超过1米每平方秒,加速度的方向可以瞬间改变成任何方向,加速度的大小可以瞬间改变成1米每平方秒以内的任何大小
问:
(1)应如何操纵赛车,才能在遵守行车规则的前提下,到达终点所需的用时最短?这个最短的用时是多少秒?
(2)如果换成规模更大的赛道,应如何编写程序,读入赛道,输出最佳的操作序列和最短用时? 这个离散化一下结果如何?时间作为目标函数感觉不好分析。 把时间离散化成0.25秒,让加速度每0.25秒变化一次,模拟退火算法的求解结果如下:
成绩大概是10.55秒,加速度大小始终是1,加速度的方向如下图所示:
这个加速度的操作序列好像没啥规律。不知道把时间分得更细之后,结果会怎样呢? 把时间分的更细,每0.125秒为一个时间段,让加速度每0.125秒变化一次,模拟退火算法的求解结果如下:
成绩大约是10.50秒,加速度的大小始终是1,加速度的方向如下图所示:
这个加速度的序列好像还是没啥规律,可能还没有优化到最佳成绩 由于模拟退火算法难以找到最优解,于是换成粒子群算法(把时间步长恢复到0.25秒),求解结果如下:
最快到达终点的那辆赛车,每0.25秒的加速度在模拟退火的解的基础上,应分别增加
0.1*
弧度,它的成绩比模拟退火的成绩快0.02秒左右
粒子群算法的求解步骤如下:
在模拟退火得到的解的基础上,每一步都尝试 {逆时针旋转加速度方向0.1弧度、保持加速度不变、顺时针旋转加速度方向0.1弧度} 这3种方案
于是理论上:
经过第1步的模拟,原来的1辆赛车就分身成3辆赛车
经过第2步的模拟,原来的3辆赛车就分身成9辆赛车
经过第3步的模拟,原来的9辆赛车就分身成27辆赛车
……
经过第n步的模拟,原来的3^(n-1)辆赛车就分身成3^n辆赛车
就像从起点发射了一群粒子一样,哪个粒子最先到达终点,以后赛车就按它的路走,因此称为粒子群算法
但实际上,大部分粒子都撞墙后消失不见了,不再产生后续的分身,只有很小比例的粒子顺利到达了终点
接下来从存活的那些粒子里找出最先到达终点的那个粒子,学习它的操作序列,即可完成一轮优化
接下来不断重复上述步骤,就能找到加速度方向精度为0.1弧度的最优解
接下来逐渐调低旋转加速度方向的幅度,多次重新求解,就能找到加速度方向精度更高的最优解
#####
将旋转加速度方向的幅度从0.1逐渐调低至0.0001,多次重新求解
结果成绩提高到10.46秒后就难以提高了
这个成绩对应的路线图如下:
这个成绩对应的加速度方向如下:
与模拟退火的操作序列相比,这个序列更光滑 把时间分的更细,每0.125秒为一个时间段,让加速度每0.125秒变化一次,粒子群算法的求解结果如下:
最终成绩是10.41秒,比模拟退火的成绩好多了,加速度的方向如下:
这个加速度序列比模拟退火得到的序列光滑多了,唯一不能解释的现象是:
【当时间段长度是0.25秒时,加速度方向序列的尾部是平的,
但是当把时间段细分到0.125秒时,加速度方向序列的尾部是翘起来的】
我已经检查过了两组解,确实是最优解,已经没法继续调优了,所以我不知道该怎么解释上面这个奇怪的现象。 楼上sxyjtd发贴问这道题和数学有什么关系(楼上sxyjtd的发贴可能被删除了),回复如下:
这是编程擂台板块:
----------------------------------------------
编程擂台 今日: 3 |主题: 283|排名: 22
版主: KeyTo9_Fans
■ 范畴:摆擂、攻擂,各显神通,源码or程序不限。
----------------------------------------------
这个板块是可以编程解决问题的 顶!
一看到这个问题,就觉得不简单,是个难得的好问题,只是还没找到相应特别好的解决方案。
楼主已做了不少创造性的工作,并分享出来,希望感兴趣者有能力者也参与到这个问题的讨论中来。
页:
[1]