蚁群背包问题matlab代码,蚁群算法--背包问题

ACO在提出之时主要用来解决旅行商问题(即TSP，不清楚的可以百度TSP)。旅行商问题也是一个经典的NP完全问题，比较传统的解法有贪心算法等，在问题规模增长时，传统算法的求解效率大大降低。ACO的灵感来源于蚂蚁搜寻食物的过程，对于寻路问题有天然的优势，在旅行商问题上的成功应用证明了这点。

ACO最核心的两个公式如下：

第一个公式计算蚂蚁选择下一个要去的地点的概率。第二个公式计算蚂蚁走过每个地点后，每个地点上残留的信息素。对于不同的问题模型，这两个公式中参数含义不一样，具体计算时，过程相似，细节不同。

本文主要讨论ACO应用在求解简单的01背包问题上。关于背包问题的描述，参看我的博文遗传算法--背包问题。

说了这么多，直接上代码，代码就是最好的讲解：(scala语言实现)

package main.scala

import scala.collection.mutable.HashSet

import scala.collection.mutable.ArrayBuffer

import scala.io.Source

// 定义蚂蚁

class Ant(val knapsack_data:ArrayBuffer[(Int, Int)])

{

val item_num = knapsack_data.length // 背包中物品数量

val iter_all_item_set = new HashSet[Int]() // 每次迭代所有物品的集合(均保留下标id)

val iter_legal_selected_set = new HashSet[Int]() // 每次迭代所选的合法物品集合

var pheromones:Array[Double] = _ // 物品信息素值的引用

val LIMIT_WIGHT = 1000 // 背包的总重量限重

var iter_selected_weight = 0 // 每次迭代所选物品的总重量

var iter_selected_value = 0 // 每次迭代所选物品的总价值

def this(data:ArrayBuffer[(Int, Int)], pher:Array[Double]) = {

this(data)

pheromones = pher

}

// 根据信息素计算选择概率，选取下一个概率最大的爬行位置(物品)

private def select() = {

var sum = 0.0

for(id

{

sum += (pheromones(id) * knapsack_data(id)._2 / knapsack_data(id)._1)

}

// 每个物品被选中的概率集 (概率，下标id)

val probabys = iter_all_item_set.map(id => {

val Pj = (pheromones(id) * knapsack_data(id)._2.toDouble / knapsack_data(id)._1) / sum

(Pj, id)

}).toArray

var max = (0.0, 0)

for(i

if(i._1 > max._1) {

max = i

}

}

max._2

}

// 每次迭代前的处理工作

def before_each_iter() = {

iter_selected_weight = 0

iter_selected_value = 0

iter_all_item_set.clear()

iter_legal_selected_set.clear()

for(i

{

iter_all_item_set += i

}

}

// 蚂蚁爬行，从起始点开始，选取一条路径，即生成一个所选物品序列

def go() = {

while(iter_all_item_set.nonEmpty)

{

// 选取下一个概率最大的物品

val pos = select()

if(iter_selected_weight + knapsack_data(pos)._1 <= LIMIT_WIGHT)

{

iter_selected_weight += knapsack_data(pos)._1

iter_selected_value += knapsack_data(pos)._2

// 若不超过总重量，加入到合法序列中

iter_legal_selected_set += pos

}

iter_all_item_set -= pos

}

}

def resultString() = {

val ret = new ArrayBuffer[Int]()

for(i

{

ret += {

if(iter_legal_selected_set(i)) 1

else 0

}

}

ret.mkString(",")

}

}

object ACODemo

{

val KNAPSACK_DATA_FILE = "knapsack.data"

val INIT_PHERO = 1.1 // 每个物品上信息素初始值

val ITER_RESERVE_PHERO_RATE = 0.7 // 每次迭代每个物品上信息素的保留率

val ANTS_NUM = 20 // 蚂蚁数量

val ITER_NUM = 30 // 迭代计算次数

// 读取背包问题的初始数据

def readKnapsackData(path:String) = {

val list = new ArrayBuffer[(Int, Int)]()

for(line

{

val strs = line.split(" ")

list += ((strs(0).toInt, strs(1).toInt))

}

list

}

// 初始化蚁群

def initAnts(data:ArrayBuffer[(Int, Int)], pher:Array[Double]) = {

val _ants = new ArrayBuffer[Ant]()

for(i

{

_ants += new Ant(data, pher)

}

_ants

}

// 找出最优的蚂蚁个体

def findBestAnt(ants:ArrayBuffer[Ant]) = {

var best = ants(0)

for(ant

if(ant.iter_selected_value > best.iter_selected_value)

best = ant

best

}

// 更新所有物品的信息素

def updatePheromones(pheromones:Array[Double], ants:ArrayBuffer[Ant],

data:ArrayBuffer[(Int, Int)]) = {

for(i

{

// 计算每个物品的信息素增量

var increment = 0.0

for(ant

{

val delta = {

if(ant.iter_legal_selected_set(i)) data(i)._2.toDouble / ant.iter_selected_value

else 0.0

}

increment += delta

}

// 更新该物品的信息素

pheromones(i) = ITER_RESERVE_PHERO_RATE * pheromones(i) + increment

}

}

def main(args: Array[String]) = {

// 背包数据，每个元素为(weight value)

val data = readKnapsackData(KNAPSACK_DATA_FILE)

val pheromones = Array.fill(data.length)(INIT_PHERO) // 所有物品的信息素值

val ants = initAnts(data, pheromones)

for(i

{

for(j

{

ants(j).before_each_iter()

ants(j).go()

}

val best_ant = findBestAnt(ants)

println("第" + i + "代，总重量：" + best_ant.iter_selected_weight + "，总价值："

+ best_ant.iter_selected_value + "，物品序列：" + best_ant.resultString())

updatePheromones(pheromones, ants, data)

}

}

}

首先从文件“

knapsack.data”中读取背包物品数据，

背包物品的数据组织方式参看我另一篇博文

。然后初始化物品上的全局信息素、初始化蚁群，接着开始不断的迭代计算，直到迭代结束。

如何设计选择概率的计算方式和信息素的更新方式，直接影响到ACO算法性能，优化ACO通常从这两方面入手。本文在计算物品的选择概率时，只针对未选物品，已选物品的概率均为0。在更新物品的信息素时，每只蚂蚁都会影响到该物品的信息素变化，只要蚂蚁的选择路径中加入了该物品，更新时都要考虑进去。

经测试，本文中的ACO处理01背包问题，拥有较快的解收敛速度，能够比较快速的找到一个优质解。