Posts tagged 算法

人工神经网络-ANN

最近SC AI做得差不多了,忽然想到应该写一写关于ANN和GA的科普文章呢,毕竟自己学习只是一部分,跟大家分享也很重要嘛。自己叙述一遍的话,也能考察自己掌握的程度。 ANN, artificial neural network, 即人工神经网络,是机器学习的一种模型。我学习这个其实也是读教科书,用的是卡内基梅隆大学那本machine learning。 所以先说说机器学习吧。机器学习的基本思想就是不通过编程来让计算机完全遵守人指定的死板的流程,而是通过定义一个可学习的模型,之后向这个模型不断添加<问题,答案>这样的对(正式名称是<输入样例,目标输出>),来让计算机通过经验判断下一次接收到问题的时候,应该做出怎样的回答。 其解决方案就是根据每一次的计算机回答和人指定的标准答案进行对照,假如相符,则给予鼓励;假如不相符,则给予批评(即正激励和负激励)。通过不断的训练引导计算机逐渐获得对相关知识的理解。 人工神经网络是机器学习的一个解决方案,即采取仿生的神经元结构来对计算机进行训练。由于人的神经元的复杂性,目前用于计算机研究的神经网络通常采取的是一种简化模型。他令神经元有一个输出和多个输入。神经元通过对所有的输入进行加权求和计算出结果,并以这个结果作为输出(可以想象出来,训练一个神经网络,其实就是训练他使得每一个神经元都得到正确的权值组合)。为了保持简洁性,每个神经元的输入和输出都最好保持在0~1之间。于是这里采取了一个挤压函数,将实数域映射到0~1之间的一个小集合上。通常采用的挤压函数是sigmoid函数,sigmoid(x)=1/(1+exp(-x))。当然也可使用其他有类似特点的函数变体啦。定义好神经元之后,须将神经元根据问题需要构造成神经网络。目前业界通用的较为稳定的神经网络是单向无环的结构。往往采取三层。 第一层是输入层,根据需要,要把问题转换为一个编码,并依次作为输入给各个输入曾神经元赋值。例如,用于人脸识别的神经网络,可采取一个人脸照片的32×32的缩略图作为输入,这样的话就需要1024个输入,每个输入是0~255的像素灰度信息。有比如要从今天的天气情况推算明天的天气情况(当然实际是不可行的。。),可将想要考虑的所有天气特征依次作为输入,并传输给各个神经元。 第二层是隐藏层,它的作用是增加神经网络的复杂度,从而使神经网络可以表达更复杂的函数逻辑。已经证明,任意函数可被三层单馈神经网络(一个输入层,两个隐藏层和一个输出层)以任意精度逼近。但是,更复杂的函数就需要更多的神经单元来表征。由于我们在实现神经网络之前,往往并不能确定问题的复杂度,所以隐藏层采用的神经元数量往往是要靠经验得出的。当然也有一些动态修正的方法可以在训练的过程中增加或减少隐藏层的单元数量。 第三层是输出层,输出单元一般不使用挤压函数处理,而是让他输出线性的数据,以便同实际问题相联系。输出层同样要根据实际问题来编码。例如在人脸识别的应用中,可采取两个输出,一个表示“是人脸”,一个表示“不是人脸”,这里输出还是在0~1之间的。可采取一个阈值来确定真假,例如用>0.7表示真,<0.3表示假,之间是模糊状态。之所以采用两个输出而不是自然想到的一个,是为了稳定性。当两个神经元的输出相符时(例如“是人脸”输出0.9,“不是人脸”输出0.1),可认为模型正确得出结论;而当两个输出不符时(例如均输出0.7),则表示模型无法准确判断。 建立好模型之后就是训练了。这里采取的方法称作“梯度下降的反向传播算法”。之所以称作梯度下降,是说根据人确定的正确答案和计算机通过神经网络给出的答案之间应该会有一个差距。将这个差应用到得出这个结果的输出层上,就能得出输出层的每一个权值应该向哪个方向调整。注意到神经元输出是输入的加权和,所以权值较大的那个分量对于结果的贡献越显著,因此在训练时对他的反馈也应该相应得更明显。数学上采用方差对于权值的函数形成曲面的梯度来描写这个特征。沿着梯度下降到曲面的最小值(有时只能达到局部极小值),就是训练成功了。由于梯度从概念上说是一个无穷小增量,这里只能定义一个较小的“学习速率” η 来作为每次修正权值的增量基准。η取得太大会导致无法达到曲面的最小值(总是越过他),而太小则会导致训练的迭代次数过多,同时也会使得只能达到局部极小值(无法越过局部最小值的谷底)的问题变得严重,因此也有采用变化的η值,例如逐渐减小的η(加快训练速度),又或者带有冲量的η(越过局部最小值的谷底)。这里它的取值变成了一个复杂的研究课题这里不表了。 这就解释了什么叫做“梯度下降”,再来解释反向传播。前面说到根据输出o和标准答案t可以得到一个方差,从而修正输出单元的权值,但如何修正隐藏单元的权值呢(输入单元只有一个输入,因此没有权值也无需训练)?这就是要用到反向传播的地方。既然已经得出了修正后的输出层权值,就又可将输出层的每一个输入(即隐藏层的每一个输出)的实际值和目标值,将修正“反馈”到上一层去。当然仍然需按照每一个权值贡献不同按比例反馈。反馈之后即可得到这层单元的“目标值”了,在用这个目标值在这一层做梯度下降进行训练,这样做一直反馈到输入层为止。 总之假如能够训练使得函数达到最小值,就表示训练成功了。因为它的含义是合适的权值取值,使得模型的输出结果o和标准答案t之间的方差最小。注意由于输出单元往往不止一个所以这里o和t都是向量。方差指的是每一个单元的输出方差再求和。 好吧这些就是理论讲解啦。当然实际应用的时候对于不同的问题会有不同的变形。无论是学习速率,挤压函数,还是权值的梯度下降算法,都可以有这样或那样的改变。这些就是一方面凭经验,另一方面也靠创造性的想象力和“尝试-失败-尝试”的方法来验证啦~ 链接: 维基百科-人工神经网络 http://en.wikipedia.org/wiki/Artificial_neural_network 维基百科-反向传播算法 http://en.wikipedia.org/wiki/Backpropagation 维基百科-梯度下降算法 http://en.wikipedia.org/wiki/Gradient_descent 维基百科-机器学习 http://en.wikipedia.org/wiki/Machine_learning 图书 《机器学习》 http://www.cs.cmu.edu/~tom/mlbook.html

单汇图的环的处理

最近还在搞 SC AI。 由于每个单位仅能攻击敌人,所以其攻击链类似一个树(其每一个节点都是多源单汇的,类似于树的有一个父亲但有多个儿子的情况)。唯一不同的是这个树的树根也可能攻击一个敌人,从而形成环。但是由于一个单位只能攻击一个敌人,所以在一个独立的联通分量里面,最多只有一个环。 现在我在考虑使用递归来遍历这个图,然后得出每个单位在目前情形下再有多少轮会被消灭的报告。之所以要遍历,是因为有这种情况:a攻击b。c和d都攻击a。b攻击a。c和d又各自同时被两个单位攻击。在这种情况下,表面上看a遭受的攻击最多,他应该选择撤退。但是假如考虑到c和d的血量,或许c和d会在a之前被消灭。之后a遭受的攻击就不比b多了。所以在某种情况下,a应该采取的策略是继续进攻而不是撤退。 以上是我决定计算攻击链的理由。 于是在采取递归遍历这个图的时候,关键问题是怎样避开这个环。首先是如何发现这个环,然后是如何处理他。关于发现,我现在采取了一种非常低级的办法。我使用了一个静态的数组,记录每一次递归遍历到的节点。假如下一次递归遇到了这个数组里面的节点,则表示发现了环,并开始调用处理环的函数。我相信关于发现环一定有更好的算法。可惜暂时没有时间做了,加上问题都是节点数量在20以下的,所以也没有必要做得很复杂。 至于处理环的方法,我决定在这个环上寻找最早被消灭的节点。由于仅可能有一个环,所以先把除了环之外的分支计算完毕,之后将这些分支的贡献都先计算掉。此时得出的最先被消灭的单位,在环贡献也计算的情况下一定也是最先被消灭的。因此此时可以先计算这个节点的消灭轮次,然后在这个位置将环打开,并按照无环的逻辑去计算每一个节点。 这个问题抽象出来是个很有趣的图论问题,今后应该可以继续深入思考他的意义,并跟其他图论问题做一些比较,不过暂时先放在这里吧。

SC AI设计的强力纠错

昨天熬了一夜之后,在非常兴奋以及脑袋糊掉的状态下写了最近的工作进展和思路。。可惜大多数都是语无伦次。。 今天在仔细读过之后,发现,大多数的想法,都是在写前面几个段落的时候和快要写完的时候不一样,结果导致前后很多矛盾,再加上使用了很多似是而非的术语,让整篇文章几乎没有说对的地方。。 这里也不可能把所有的毛病都改掉了,不过也好上一篇文章成了只有我自己才能看懂了胡言乱语。。。 先说说神经网络吧。上一篇文章多次提到神经网络,其实是指的几个不同的东西。并且这几处都没有给出神经网络的构造。而真正给出构造的一处,即采取各单位相连以广播行为等的那个构造,其实不是神经网络,最多只能说是一个参考神经网络而设计的通信模型。在Holland的一本叫做emergence的书中曾经提到过一种称之为元胞结构的构造,可能这个设计更近似于那个构造,但也还是有很多不同之处。应该说这是一个实验性的构造,也只是我的一时想象,暂时不能说他能够给AI设计起多大的帮助。 而至于使用神经网络结构来学习几项重要的特征,比如是否被封闭(能否逃离),目标健康程度能否在一击内消灭(计算护甲、hp、shield等),同理也可用上述原理计算自身是否安全。这些特征采用神经网络学习是有可能的。神经网络是一个相对静态的结构,必须用于学习能直接得到结论的结果。当然这里我说的神经网络是指没有环路的单馈三层神经网络了。这是一种成熟的技术,可以在AI学习中有很多应用。但也正是这个原因,使得他无法应用于博弈模型这样的无法立即得到反馈的机器学习中来。 昨天文章中说到的“估值函数”也是笔误,其实我想说的只是找到了几个重要的特征值,而没有希望直接设计估值函数。其实我昨天的想法是,通过设置神经网络或者类似于神经网络的其他模型,只要找到了估值特征值,令模型自行学习权值,则估值函数可以通过机器学习得到。这点也是昨天没有说清楚的。。 总之目前的状态是初步的想法有了,但是很多具体细节还没有想清楚。并且前面提到的最重要的部分,也就是类似于“元胞结构”的部分,还有很多没有明确定义的东西。这些地方还需要继续想清楚。 以上

SC AI 神经网络模型和遗传编程

今天wp升级,手欠顺便升级了一下theme,结果忘记备份导致原先的更改全部消失,又重新折腾了好久。bo的外观稍稍有点变。。 昨天由于一整天没有干正事,导致晚上相当悲剧。。熬了一整夜,不过 SC AI的神经网络模型基本上有了框架了。接下来就可以根据各种YY往里面增加参数、估值函数和各种加权了。 目前仍然以考虑zealot为主,不过我发现对zealot适用的模型,对dragoon同样适用,只是需要让他重新适应一次估值函数的权值就可以了。因此这里还是继续仅讨论zealot。首先,确定每个单位拥有进攻和溃逃两套互不相干的策略机,然后给定一个决定是进攻还是溃逃的决策机制,就可以了。 这个决策机制我称之为勇气。当估值函数超过阈值的时候,认为这个单位士气高涨,会继续进攻,而当估值函数低于阈值的时候,这个单位士气低落,会决定溃逃。如果以zealot的攻击范围为单位,将zealot周围区域分成8个方格,则可将每个方格内是否有敌军或友军单位,作为一个神经元输入,更远的敌军或友军单位,通过更多的神经元相连间接得到,任何单位决定进攻任何目标或溃逃都需要作为一个信号向外部发送并引起这个神经网络内的其他神经元的策略改变。参考神经网络模型的疲劳机制,当单位持续士气高涨的时候,会将阈值按照一定的因子提高,使之勇气下降,同理,当单位持续溃逃的时候,会将阈值相应降低,使之变得较为容易参战。这个可变的阈值,可称为单位的勇气。 勇气的估值参数主要有如下几点:自身hp和shield,正在攻击自己的敌对单位数量(以及他们的被攻击情况和健康情况),自己正在攻击的敌对单位hp和shield。考虑这些的目的主要是为了估算自己能否在生存情况下消灭正在攻击的敌人。当然这个逻辑我不准备放入估值函数中,而令其通过神经网络训练学习得到。通过给定不同的加权估值,经过训练应该能得到和人思考出的相似的结论。 假如勇气决策为进攻,则选取攻击决策机,并令其给出一个攻击指令。攻击指令可以是:攻击最近的敌人,攻击hp和shield按照某种权值计算后健康程度最差的敌人(这和需要几次攻击才能消灭敌人有关系,需要折算护甲,攻击类型和目标体积的关系等复杂内容,例如Dragoon拥有20的damage,可是攻击被打光shield的zealot时一次攻击只能造成9hp左右的伤害,这是因为dragoon的爆炸攻击类型对zealot的小型单位只能造成一半伤害,而同时未升防御的zealot拥有1的armor,会抵消10%左右的伤害),攻击盟友正在攻击的敌人,攻击威胁最高的敌人,以及保持目前攻击目标不变。而得到这个攻击指令的效果,又可以采用:攻击单位命令,移动攻击命令,巡逻命令,移动/待命等命令来实现。因此想要使用一个模型来模拟全部的可能性,实在不可能。这里必须采用遗传编程的方式,令不同的策略模型在竞争中互相杂交和进化,最后得到较优的结果。 溃逃机制主要需要考虑的是两种特殊情况,即被友军封闭和被敌军封闭。假如溃逃单位被友军封闭,最好的策略是能够通过该单位向四周发送一条信号,而使合适的单位为其让路。这个信号同样可以用于保持阵型,即“最佳防御位置”的确定。而假如溃逃单位被敌军封闭,则应该立刻变为英勇,因为无论如何也逃不出去了,应该给敌人以最后的伤害。但如何确定某单位是否被封闭了?BWAPI似乎提供了函数,但我暂时还没有测试。否则使用周围单位的位置和权值,让神经网络自己去学习也是可行之道,不过似乎大材小用了…… 以上就是最近一段时间测试和思考的内容。另外经过很多测试,对BWAPI和星际争霸游戏的各种特点也慢慢熟悉了,相信对接下来的开发会有帮助吧……

旅行商问题的一点笔记

最近朋友跟我讨论了一个类型的旅行商问题。原版的旅行商问题是说,给定一个图,给定起点和终点,求不重复经过任何节点的最短路径,遍历全部节点。而他的问题是,仍然不许重复经过任何节点,但是不要求路径遍历全部节点,而是遍历某一个给定的关键点集,求最短路径。问题里面对图没有做任何限制,图可能包含数千节点,不过关键点集是充分小的,比如只有5个关键点,这样。 一开始我没听清楚题目,以为这个问题跟斯坦纳树有什么关系。(所以才会写了上面一篇note。。)不过后来知道不许重复经过节点,那么这种想法就没有用了。 不过既然关键点集充分小,求的又是路径,那么几个关键点必然只能依次经过。可以尝试所有关键点的排列,依次求最短路径。比如说5个关键点,也只需要算120次。还算可以接受吧。并且假如采取分支定界,其实还是可以减去很多分支的。当然可以构造出几个关键点无论怎么排列,路径都等长的情况。比如所有两两点间都有路径长度为1的任何图,都是这样。。。不过假如是工程上使用的话,可能还有其他办法可以提前退出,比如求出“足够好”的解,或者算了很长时间,一直没有找到更好的解,之类的。。这个就可以根据需求而定了。 不过朋友比较担心的是割点的问题。割点是说,一旦去掉这个点,则图会被拆成两个独立的联通分量。就是说从图的某些点出发,永远也无法到达图的另外一些点了。。之所以担心这类点,是怕一旦算法的前面走过了这类点,那么由于存在不许重复任何节点的限制,可能导致某些点无法经过了。那么这个割点至少有两种情况。就是这个割点会导致关键点被割掉,或者只会导致非关键点被割掉。 导致非关键点被割掉的那种割点,可以直接收缩为一个点。因为题目并不要求遍历非关键点。并且求出的路径绝不可能进到那个割点后面去(因为1.里面没有关键点,2. 进去就出不来了)。那么至于说会导致关键点被割掉的情况呢?暂且也把他收缩为一个点吧。如果不断这样收缩,整个图就会最终退化为不含割点的图。并且最后一次收缩的割点应该不会超过两个。假如超过两个,那么这个图是无解的。因为总有一些关键点,你要经过一个割点才能进去,然后就出不来了。至于不超过两个,那是说起点和终点可以从割点经过。当然这个是欧拉说的啦。。 比如上面的图,每个椭圆表示里面有一坨点,并且里面的每个点都至少有两个入度。假如上图的三个小椭圆里面都有关键点,那么这个题就无解了。假如任何一个小椭圆里面没有关键点,那么就可以直接去掉。 最后肯定只有不超过两个小椭圆里面是有关键点的。比如上图的红色椭圆。可以暂时收缩成一个点。 所以最后一次收缩的割点,不会超过两个。 那么其实这种收缩可以重复进行,于是可以写出递归代码来解。当然现在问题就转化成,对于没有割点的情况,怎么解这个问题。 当然其实问题的难点,也正是在没有割点的情况下吧。。还是继续前面那种遍历所有关键点顺序的那个思路,这回每次需要考虑的关键点都变少了(好吧也可能没变少,至少不会变多!!)。接下来的事情可以参考旅行商问题的一般解法来求吧。。因为不是我的题目,所以没有继续去查。。同样是做个记录留下来吧。。还是方便以后捡回来。。

斯坦纳树的一点笔记

大三的时候做了一道斯坦纳树的题,最近几天朋友跟我讨论某个问题,忽然觉得跟那时候的做法很类似,结果发现自己没有留下任何材料。想了半天把那时候的想法回忆起来了。当时没有留记录是因为想法太简单,算法性能太差。不过现在想想无论好坏,啥想法都应该记下来,以后至少可以在这个基础上继续走。 Steiner Tree, 就是说给定一个图,和他的节点的一个子集。求包含该子集内所有节点的最小生成树(不要求包含全图的所有节点)。其实是算法老师留的作业,那时候也没当回事周末随便写了点。结果发现这个居然是一个NPC问题。只好临时想了一种解法。还是沿着prim算法的思路走,每次向已生成好的树里面增加一个新节点。只不过这次,每次都只增加关节节点集里面的节点。而寻找节点的时候,需要用Dijkstra算法。并且找到需要加入的关键点后,也需要把路径上的其他非关键点也加入进正在生成的树上面去。说到Dijkstra算法,复杂度是n^2, 再加上prim算法复杂度也是n^2,复杂度岂不是到达n^4?其实没有。因为每次使用Dijkstra算法,都把某一个点到其他所有点的路径长度都求出来了。而最终的结果,最坏也不过把所有节点两两之间的最短路径求出来,相当于填了一张n×n的表,n是节点数量。用一次Dijkstra算法可以填一行。总共n行所以复杂度是n^3。恩这里算是用到了动态规划。性能还算是可以接受吧。不过这个算法明显求不出精确解。我也没有证明过他求出的解究竟能多逼近,或者在哪些条件下能求出足够逼近的解。只不过是当时老师给的样例输入正好碰上是返回正确结果,就这样交卷了。 恩后来又在网上查了很多资料,貌似斯坦纳树研究的人还是很多的。不过搜到的资料大多是些没法下载的论文。。。所以也就荒废了没有继续看下去。。今后有机会在继续看吧。这次只是把过去的思路记录一下以后方便捡起来。