数组内容随机排序问题请教

灰袍法师

原帖由 lanyf 于 2011-4-7 07:15 发表

叶片前期布置仅仅是为后期做准备
待到整体组装完成后，要对整体做静平衡
而且单张叶片重量精度一般.01kg，所以只有结果在。01就算是最优解（可接受解解 ...

wow，0.01kg的要求是非常高的啦，因为你的叶片重量的单位精度是1kg，一般来说，最后计算的结果也将会是1kg左右，顶多下一个数量级0.1kg，0.01kg几乎是不可能的事情！

如果是计算你上一次的帖，13叶片的数据，那么上一次靠excel公式计算，1万次随机是30秒

本附件全用VBA计算而且直接查力的分量，速度快了300倍，计算100万次也就几秒，精度高达0.0x

对于随机的25叶片，随机100万次大概12秒，大概是 0.2-0.5 kg的精度

嗯，对随机算法而言，高速度就是高精度吖

如果结合启发方式的搜索算法（遗传算法，模拟退火，贪婪）等等，应该可以做到0.01kg的精度要求，有空再说了。

以上各种算法其实也是基于随机算法

你在每次随机排位置后，再对换两个叶片的位置使结果更好，那就是结合贪婪算法

如果在随机排位置之前，给某些叶片排在某些有利位置的概率更高，就是遗传算法，当然，有利位置，更高概率这些都需要保存历史数据并加以计算，比较繁琐

如果再给遗传算法，或者贪婪算法一个随机的概率如0.05，在此概率下不向最优结果的方向调整叶片的位置，而是随机调整，那么就是模拟退火算法

其实这些改进，都是为了避免单纯随机算法收敛太慢（达到高精度需要很多很多次随机计算）

所以在随机排位置之余，加入根据历史数据进行猜测（启发）的调整方法，从而使优化的目标值收敛更快。

如果把问题看作找出地球表面海拔最高的位置（珠穆朗玛峰的顶点）

那么随机算法就是随便找一个点，看看是不是最高，显然不可能找到最高点，但是很可能落在珠穆朗玛峰区域

贪婪算法就是随便找一个点，然后在这个点往四周移动一定范围，移动方向是最陡峭的方向，即随机爬附近的山，很显然可能爬上了泰山，但爬上珠穆朗玛峰的几率很低，所以一定要结合随机算法，随机爬好多座山，总会爬到珠穆朗玛峰的某座山峰（但也不一定是最高峰）

遗传算法就是记录随机点的坐标，如果发现某些坐标的点都比平均水平高，那么以后就优先在这些坐标附近选取点，显然，优先坐标到了最后，必然是爬过的最高的几座山，但这几座山不一定包括珠穆朗玛峰，即使包括，也不一定是最高峰

模拟退火算法就是得到了优先坐标以后，以一个低概率选择任意点，以一个高概率选择优先坐标，这样可以避免遗传算法爬来爬去都是几座小山，也可以避免找到了珠穆朗玛峰或者青藏高原以后，还花过多时间去尝试其它低海拔地区

总的来说，随机算法是一定要的，在此基础上选择怎么再快速优化，就产生了不同的启发性算法。每一个都不能保证全局最优解，不过每一个都会比单纯随机算法收敛更快，当然作为代价，要写的代码也肯定复杂多了。而且，如何优化，都是要针对问题去设置的，每个问题的优化方法都不一样。
就你的问题而言，贪婪方法可以看一下正弦合力是不是正数，然后检查是否可以交换两个正弦力来减少这个正数，不过复杂的地方是，交换两个叶片不仅导致正弦合力的变化，还要考虑余弦合力的变化，所以需要找到同时优化两个合力的叶片位置交换

遗传算法比较麻烦，也许是汇总记录某个叶片的位置，或者是某个叶片落在四个象限的概率，或者是一对叶片的位置，找出最优良的“基因”才能决定如何遗传下去，这些都要代码写出来以后才知道怎样遗传比较好

不过我觉得既然后续步骤还可以调整静平衡，也没必要搞得太复杂，随机个1000万次好了，顶多加个贪婪方式的叶片交换。

几十吨的风扇，真的需要把合力优化到0.01kg吗？估计静摩擦力都不止这个数了。。。。。。而且如我开篇所言，输入数据当中未必存在这样的解

最后，你的标题是不是要改一下。

[ 本帖最后由 灰袍法师 于 2011-4-8 05:53 编辑 ]

lanyf

原帖由 灰袍法师 于 2011-4-7 20:46 发表


wow，0.01kg的要求是非常高的啦，因为你的叶片重量的单位精度是1kg，一般来说，最后计算的结果也将会是1kg左右，顶多下一个数量级0.1kg，0.01kg几乎是不可能的事情！

如果是计算你上一次的帖，13叶片的数据， ...

佩服 太佩服啦~~~
谢谢 我会好好研究您这篇文章的
关于概率算法还有启发式算法
我研究了半天
只有您讲解的这么透彻
一下子让我清楚了是怎么回事
其他网上搜来的论文 都不晓得他们在说什么呢
一点实际的内容都没有
呵呵~~
我再仔细消化下您的文章 争取把他变为我的知识
再次说声 谢谢~

灰袍法师

原帖由 lanyf 于 2011-4-8 07:05 发表

其他网上搜来的论文 都不晓得他们在说什么呢
一点实际的内容 ...

不奇怪，好多中文论文都只是你抄我我抄你，废话连篇，作者本身都没弄懂。。。。。。

附件是一个非常简单的遗传算法（或者说进化算法，基因算法）

可见同样的耗时，遗传算法得到的结果通常比单纯随机算法要好

当然，这个遗传算法真的是非常简陋。。。。。。算法如下：

第一步：选择优良种子

先随机生成指定的若干个方案（如10000个），选择其中最好的若干个（如100个）作为种子

通常种子的数量不宜太少（否则很容易种群退化），也不宜多（否则计算太耗时），当然最佳值是多少，那就天知道了，我个人认为1%或者0.1%比较合理，或者100-1000比较合理。

这一步用堆结构来实现，因为堆这种结构，可以保证直接取出堆中最好的一个元素

第二步：变异
随机选择种子的一段基因，把这一段基因内部的排列打乱，然后计算打乱后的得分

（当然也可以杂交，即把两个种子的两段互不相干的基因合并）
（或者也可以改良，即用贪婪法尝试交换叶片，使结果更好）

所有种子都变异若干次，而又从所有变异结果选出最好的100个，这时候就得到了第一代变异后代

重复变异若干代，每一代都留下最好的100个作为下一代的种子。。。。。。

最后一步：把当前最好的100个变异后代，选出最好的一个就是最终结果了。

可以看出，遗传算法有非常多的参数，而改变参数将大大影响算法的效率。

怎样定义基因，这个是最重要的，附件简单采取 连续的叶片就组成一个基因，这样估计并不是最好的定义方法，毕竟叶片都几乎是成双成对的。

而基因的变异长度，变异的剧烈程度，变异多少代等等都大有影响

更不要说再加上杂交和改良了，相当的复杂啦。。。。。。

[ 本帖最后由 灰袍法师 于 2011-4-9 04:46 编辑 ]

lanyf

原帖由 灰袍法师 于 2011-4-9 04:39 发表


不奇怪，好多中文论文都只是你抄我我抄你，废话连篇，作者本身都没弄懂。。。。。。

附件是一个非常简单的遗传算法（或者说进化算法，基因算法）

可见同样的耗时，遗传算法得到的结果通常比单纯随机算法要 ...

原来“听君一席话，胜读十年书”这样的事情真有
讲解的透彻 通俗移动
灰袍太厉害啦
能问一下您是从事什么行业的吗？
还有每次回帖好像都是凌晨4：00~5：00左右~~
是睡得晚呢 还是起的早呢~

灰袍法师

原帖由 lanyf 于 2011-4-9 08:01 发表

原来“听君一席话，胜读十年书”这样的事情真有
讲解的透彻 通俗移动

过奖过奖。

前一个附件，虽然是一个简单的进化算法，但是缺点也不少

首先，随机选择一个位置在此位置选取一段基因去变异，这就导致了进化的方向也是随机的。变异1000代似乎跟变异10代没啥区别

本附件改变一下策略

先把所有叶片排序，排序的依据是 每个叶片重量与平均叶片重量的差值

理由是：
较重（较轻）的叶片，其位置的改变对最终结果的影响最大，所以一旦选出了优良的种子，我们就假设这些种子的 较轻较重叶片 都是在一个好的位置

由此，在后续的变异过程就跳过这些叶片

结果似乎比前一种变异方式好一点，尤其是可以选种不多的时候，依然可以靠变异达到一个好的结果

如果从巨大的样本选种（如1000万），那么选种本身就等于 单纯随机试验1000万次了，当然，越大的样本选出的种子越好

然后，如果从中保留选取大量种子（如1万个），那么就可以保留更多的叶片不参加变异，即前n个叶片的所有排列数，应该跟种子数有关

如：只保留100种子，又保留10叶片不参加变异，那么10个叶片的所有排列是 10!，100种子不可能代表其中的好排列，反之亦然

变异的基因长度：这个参数代表了变异的剧烈程度，当然，变异的基因越长，产生好的后代的可能性就更高，不过计算量也呈排列增长，所以实际上每个种子的变异只能是4到6个叶片的随机交换

变异多少代：这又跟种子数，变异的基因长度有关，一般来说 5-50都是可以的

如果变异不激烈，那么变异就要多，反之则要少，不然计算量太大了

一般而言
样本数越大，种子数越多，变异的基因越长，变异的代数越多，得到的结果就越好

但计算机的计算能力无法承受，所以只能自己折中了

现在这个进化算法可以保证花1分钟时间以内，做到0.0x的优化精度，几乎比单纯随机算法的优化精度高一个数量级

可以是 1000万样本选5000种子，然后基因长度4变异30代 （即优良的种子，小的变异，中等进化程度）

或者是 10万样本选500种子，基因长度6变异30代 （即比较差的种子，较大的变异，中等进化程度）

还可以是 100万样本选1万种子，基因长度5变异5代 （即中等的种子，中等的变异，低的进化程度）

反正是选种的时间多，变异的时间就少了，反之亦然，而种子数无论如何不应该低于100，否则根本就没什么基因可以遗传下去了。

突然想起，干嘛要指定基因的变异长度和变异位置呢，让这些参数在进化过程中慢慢浮现更好

如：第一代变异是保留前三个叶片，其它叶片都参加都变异，每个种子的变异次数多
第二代保留前4个叶片。。。。。。，每个种子的变异次数较少
最后一代只变异最后4-6个叶片，每个种子变异次数极少

这样更符合“进化”的原则吖。。。。。。有待继续深入

又突然想起，对于随机算法的最大缺点，进化算法可以完全避免！
随机算法的缺点是：只能做到比99..999%的解都好，但是如果99.999%的解都是很差的解呢！！！)

如果输入数据有2个叶片重量明显高，如 7xxx kg,又有2个叶片重量明显低，如4xxx kg
那么显然一个好的解，必然是把重型叶片放置在对称的位置，而轻型叶片也跟轻型叶片组对
而随机算法得到所有特异叶片刚好都在对称位置的概率，只有 2! * 2! * 21! / 25! ，远远低于 1 - 99.999%
对于这样的情况，单纯的随机算法几乎是不可能求出任何一个好的解，而进化算法则依然轻松。

根据上述思考，我们马上又得到一个新的启发式（贪婪）算法

把所有叶片分为轻重两组，看作是两个风扇的合成！

轻的一组放置在合成风扇的单数位置，重的一组放置在合成风扇的双数位置，

分别求轻重两组的最优静平衡，合在一起作为最终结果，这样可以更快地到达最优解，因为求解两个 12叶片 和 13叶片的风扇，比求解一个25叶片要快得多，这意味着同样时间内能够尝试的组合数也多得多。

而且合成的的结果一样可以再用进化算法去优化。

[ 本帖最后由 灰袍法师 于 2011-4-10 02:13 编辑 ]

lanyf

原帖由 灰袍法师 于 2011-4-9 23:30 发表


过奖过奖。

前一个附件，虽然是一个简单的进化算法，但是缺点也不少

首先，随机选择一个位置在此位置选取一段基因去变异，这就导致了进化的方向也是随机的。变异1000代似乎跟变异10代没啥区别

本附件改 ...

再次拜读中~~~
里面的东西我要研究好几天了~~~

sunsoncheng

那个随机算法还好看明白

那个遗传算法实在看到头大,而且是遗传我上辈最差祖宗的思想

根本看不懂

灰袍法师

sunsoncheng 发表于 2011-10-20 09:23
那个随机算法还好看明白

那个遗传算法实在看到头大,而且是遗传我上辈最差祖宗的思想

不是遗传最差上代，而是把 最好的种子 建立为 最差堆 里面取出第一个元素就是当中最差的一个，替换掉最差的一个，
所以留下来的就是最好的上代

kangatang

灰袍法师 是我在EH论坛里所知道的最精通算法的一个。
今天收益匪浅。让我看到了EH的又一个亮点。谢谢谢谢。

sunsoncheng

灰袍法师 发表于 2011-4-9 23:30
过奖过奖。

前一个附件，虽然是一个简单的进化算法，但是缺点也不少

法师:

关于随机算法已懂了一点,

但遗传及变异,什么种子堆,总是不明白

起始的种子库里不是有200个?为什么后的参与更新的只用100个?

新的种子库里的合力既是以最小为标准,为什么不对进行排序,后面的新种子插入到顺序值?

选用的基因原则是什么?

如果我这样选行吗:

现在有200个种子,里面选1/4就是50个最好的,考查其位置,位置出现最多的N个(但这N个不知如何定呢,为什么这样定呢?)

位置不变,而变其它的位置?

这里的变异好象只是两个位置互换?,为什么只是两个位置互换?

真的有太多的不明白了,

请请指教!!!