python求最优解的集中算法
# 求解 1000次
后会有期的意思
for i in range(0,1000):
# 创建⼀个随机的解
r=[float(random.randint(domain [0],domain[1]))
merits# 计算成本
cost=costf(r)
# 是否更优，成本⼩为更优
if cost<best:
best=cost
bestr=r
return r
2 爬⼭法，搜索沿着某⼀个更优⽅向搜索直到⼀个极值（如下图的波⾕）
以下是python 的⼀个实现：
#domain 表⽰解空间，domain [0] 表⽰向量x第i个维的最⼩值，domain[1] 表⽰向量x第i个维的最⼤值。
# costf ：成本函数（Cost Function）
def hillclimb(domain,costf):
# 从⼀个随机解开始
sol=[random.randint(domain [0],domain[1])
#搜索解过程
while 1:
# 每⼀维都会变化以后现成⼀个新的解，共有解的长度个邻居解
neighbors=[]
for j in range(len(domain)):
# 解向量第j维在解空间，向上或者向下变化步长1（所以叫邻居解）
if sol[j]>domain[j][0]:
neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:])
if sol[j]<domain[j][1]:
neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])
# 在这⼀批寻找最优解
current=costf(sol)
best=current
for j in range(len(neighbors)):
cost=costf(neighbors[j])
if cost<best:
best=cost
sol=neighbors[j]
# 当没有更优解出现时候，认为达到某个局部最优解，搜索过程结束
if best==current:
break
return sol
3 退⽕法
前⾯的2个优化算法，都是简单往⼀个更优⽅向搜索最优解，这样如果遇到下⾯这种情况，这样很可能陷⼊⼀个局部最优解（Local optimum），最终搜索的解可能不是全局最优解（Goal optimum），为了避免这个情况，我们希望搜索过程⼀定程度允许⼀些差的解存在，因为这些解很可能存在通往最优解的⽅向上。
为了实现这个想法，退⽕法在系统早期允许差解存在，存在概率为P，这个概率越来越⼩，因为还是
要找最优解，所以系统后期基本不接受差的解，这个过程很像物体退⽕降温的过程，温度越⾼时候，分⼦运动杂乱⽆章，系统越不稳定，即可以接受差的解，当物体冷却以后，系统趋于稳定，即只接受更优解，我们⽤这个公式模拟这个过程：
茄子用英语怎么说求解过程如下（个⼈感觉直接看程序更好理解）：
附：模拟退⽕法（ Simulated Annealing；SA）最早的想法是由N.Metropolis 等⼈于1953 年所提出，在当时并没有受到重视。直到1983 年由Kirkpatrick et al. 提出蒙地卡罗模拟（MonteCarlo Simulated）概念的随机搜寻技巧，利⽤此⽅法来求解的組合最佳化问题时，才使此演算法受到重视。
以下是python 的⼀个实现：
英语口译培训def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
# 从⼀个随机解开始
vec=[float(random.randint(domain [0],domain[1]))
while T>0.1:
# 随机选择⼀个维度
i=random.randint(0,len(domain)-1)百闻不如一见
# 选择⼀个搜索⽅向
dir=random.randint(-step,step)
# 在搜索⽅向上⽣成新解
vecb=vec[:]
vecb +=dir
elif vecb>domain[1]: vecb=domain[1]
ea=costf(vec)
eb=costf(vecb)
#重新计算系统稳定性-概率p，退⽕算法核⼼
p=pow(math.e,(-eb-ea)/T)
# 更优解将替换当前解，在系统早期，温度很⾼，系统很不稳定，⾮更优解也可能替换当前解，这样做的⽬的，是避免过快陷⼊局部最优解，更⼤范围搜索最优解。
if (eb<ea or random.random()<p):
vec=vecb
# 减低温度
T=T*cool
terrorist
return vec
4 遗传算法：这个搜索过程基于⼀个假设认为全局最优解很可能存在于当前最优解种群中的下⼀代，这个下⼀代通常由当前最优解种群，通过解空间的某些维的交叉或者变异产⽣（这⾥有很多概率：变异范围概率P1，交叉还是变异的概率p2……），新产⽣的⼀代中，重新计算成本，保留⼀定数量最优解，作为当前最优解种群，如此循环经过⼏代遗传，最终在最后⼀代最优解种群中选择解。计划这个算法在另外⽂章中再详细介绍。
为了熟悉这些算法，所以实验了这个案例。除了以上算法，我们还需要编写⼀个成本函数，这个⾮常
关键，这⾥列出⼀种计算⽅法，通过计算解所描述的图上点之间的距离和线交叉情况，来评估该图分布是否均衡合理（⽐如：交叉少便于阅读），
代码如下：
def crosscount(v):
loc=dict([(people ,(v[i*2],v[i*2+1])) for i in range(0,len(people))])
total=0
# Loop through every pair of links
thanks tofor i in range(len(links)):
for j in range(i+1,len(links)):
# 计算线交叉情况
(x1,y1),(x2,y2)=loc[links [0]],loc[links[1]]
(x3,y3),(x4,y4)=loc[links[j][0]],loc[links[j][1]]
den=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)
if den==0: continue
sufferingsua=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den
ub=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den
if ua>0 and ua<1 and ub>0 and ub<1:
total+=1
#计算点互相的距离
for i in range(len(people)):
for j in range(i+1,len(people)):
(x1,y1),(x2,y2)=loc[people ],loc[people[j]]
dist=math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
onlyyou歌词
if dist<50:
total+=(1.0-(dist/50.0))
return total
效果如下：
>>> sol=optimization.annealingoptimize(socialnetwork.ssc
ount,step=100,cool=0.99)
>>> sscount(sol)
总体感觉效果不是很好，这个可能和我们的成本函数也有关，成本函数需要⽐较好的评价每个解的好与坏。
后来想，是否可以从⼀个⽐较好初始状态开始，再利⽤优化算法进⾏简单的优化，于是写了⼀个函数，根据⼈数量，先平均切割块，把关系多的⼈放在位于中间的联通性⽐较好的块，这个解作为搜索的初始值：
def init_pos(peoples,height=400):
result =[]
pos_len= round(1+math.sqrt(len(peoples)))
pos_unit=int(height/pos_len)
helf_unit=int(pos_unit/5)
#⽣成初始位置列表
for i in range(1,pos_len+1):
for j in range(1,pos_len+1):
result.append((pos_weigh(i*pos_unit,j*pos_unit,height),(i*pos_unit-helf_unit,j*pos_unit-helf_unit)))
result.sort()
#计算每个⼈的权重
people_weigh={}
for link in links:
people_weigh.tdefault(link[0],0)
people_weigh[link[0]]+=1
people_weigh.tdefault(link[1],0)
people_weigh[link[1]]+=1
people_queue=[]
for item in people_weigh:
people_queue.append((people_weigh[item],item))
people_queue.sort()
ver()
#放置⼈，根据权重⼤⼩先后放置
pos=dict([(people_queue [1],(result[1])) for i in range(0,len(people_queue))])
pos_values=[]
for i in range(0,len(people)):
pos_values.append(pos[people ][0])
pos_values.append(pos[people][1])
return pos_values
优化的⼀个结果：
由于时间关系，没有做再多的实验。。。⼏个算法优化结果都差不多，退⽕和下⼭稍微⽐随机好⼀点。
总结：
优化算法的⼀个特点往往给出的是⼀个局部最优解，不是绝对的最优解，或者说全局最优解。⼀种优化算法是否有⽤很⼤程度取决问题本⾝，如果问题解本⾝就是⽐较⽆序的，或许随机搜索是最有效的。如以下这种情况，最优解可能位于⼀个狭⼩的空间，算法通常很难找到这个最优解的途径，因为任何解决的解成本都很⾼，都很有可能被排除在外。
那是否能够事先给出⼀个⽐较优的初始解，再在这个基础在利⽤优化算法，是否可以得到较优解，我想可能是存在的，在以上的这个例⼦当中，我做了下尝试，效果感觉不是很明显，当然也有很有可能是我⽅法不对。后来分析觉得实际系统应该是使⽤类似 mass and spring 算法，这个算法也模拟⾃然界中球和弹簧的运动模型来的：各个节点施⼒企图远离对⽅，⽽节点间的连线⼜企图拉近其链接的2个节点。
附：
SOSO华尔兹是腾讯（TM）旗下搜索门户SOSO（搜搜）于2009年8⽉起新增的⼀项搜索功能。在这个页⾯⾥我们可以看到许多明星⼈物肖像被做成⼩图标，⼀个图标所链接的页⾯就是关于此图⽚⼈物的热门关联及其相关热门搜索。
SOSO华尔兹的特点在于：能够把与你要搜索的⼈物相关的其他⼈物都连成⼀个关系⽹，按照热门程度来进⾏相关联，您可以在这个页⾯中发现此⼈与其相关联⼈物之间的关系，以及在什么时候发⽣了
捎口信什么事情等等。通过点击查看详细，更可以看到关联此事件的⽹页新闻，博客，搜吧，图⽚等等。让⼈⾮常⽅便的直接找到关注点以及所关联的⼈与事。
以上内容是个⼈的⼀些学习笔记，资料⼤多源于互联⽹，有很多也是个⼈的理解，不⼀定正确，供⼤家参考。
if vecb<domain[0]: vecb=domain[0]
