人工蜂群算法分析与实现毕业论文(编辑修改稿)

人工蜂群算法分析与实现毕业论文(编辑修改稿)内容摘要：

cpf max1 (1) 式 (1)中 ， icmax 为觅食蜂 if 对应调度的最大完工期。 蜂群的平均收益率 colonypf 为   nj jc olony pf 1 m a x11 (2) 式 (2)中 ， n 为 t 时刻摇尾舞的次数 ； jcmax 为跳摇尾舞的觅食蜂 if 对应调度的最大完工期。 摇尾舞 持续时间 id 的计算公式为  colonyii pfpfd  (3) (2) 觅食算法 觅食算法在蜂群中定义了一个觅食蜂群 ,这 些觅食蜂迭代地构造出作业车间调度的解。 觅食蜂在拓扑图中沿着节点之间的边行进 ， 一次性地访遍图中从起点到终点所有的节点 ， 由此得到的路径即代表了可行解。 觅食蜂只能基于工序的优先权按照既定的可选节点清单选择下一节点 ， 这样的移动准则表示为           可选节点j ijijijijij dtdttp11 (4) 式 (4)中 ， ijp 为路径从节点 i 扩展至节点 j 的概率 ； ij 为节点 i 和节点 j 之间连边的等级数 ； ijd 为 节点 i 和节点 j 之间的启发式距离。 节点 i 至节点 j 之间有向边的等级数 9  mk mij  1 (5) 式 (5)中 ，  为偏好 路径 赋值 ，  ； k 为可选节点数 ； m 为偏好路径数 ，1m 或 0。 由于首次觅食的觅食蜂的 m 值等于 0， 则所有可选节点的 ij 赋值相同。 3 人工蜂群算 法的多线程并行实现技术 在如今的信息社会，计算机需要处理的信息量越来越庞大，需要解决的问题越来越复杂，使得计算量暴增。 通过提高单个处理器的计算速度和采用传统的“顺序 (串行 )”计算技术已难以胜任。 因此，需要功能更加强大的计算机系统和高效计算技术来支撑， 并行计算机 和并行计算技术由此应运而生。 加上第四代编程语言的出现，比如面向对象编程语言 C++、 JAVA等都提供了多线程技术，不仅可以使编程者在单处理机上模拟并行计算，还可以在多处理机上实现并行计算。 进程、 线程 与多线程 进程 、 线程 和多线程 都是 操作系统的概念。 进程是程序在一个数据集合上运行的过程 ， 它是系统进行资源分配 和调度的一个独立单位 ， 是应用程序的执行实例。 进程在运行过程中创建的资源随着进程的终止而被销毁 ， 所使用的系统资源在进程终止时被释放或关闭 ,即 具有动态性 ，从被创 建到被撤销有一个生命周期 ； 是程序的一次执行，即在指定内存中的一组指令序列的执行过程。 每个进程由私有的虚拟地址空间、代码、数据和其它各 种系统资源组成。 一个进程至少包括一个线程 (称为主线程 )，并且每个进程都由主线程开始 ， 在运行过程中可以建立新的执行线程。 线程是程序执行的基本单位 ， 通过线程可以实现程序执行的并发性、独立性和异步性。 每个线程都有自己的一套设备 (CPU、寄存器和堆栈 )，操作系统给每个独立的线程安排一些 CPU时间片，通过操作系统的调度，实现不同线程的切换。 因此， 为了充分利用 CPU，引入了多线程。 多线程是指程序中包含多个执行流，即在一个程序中可以同时运行多个不同的线程来执行不同的任务，也就是说允许单个程序创建多个并行执行的线程来完成各自的任务。 多线程是为了同步完成多项任务，不是为了提高运行效率，而是为了提高资源使用效率来提高系统的效率。 线程是在同一时间需要完成 多项 任务的时候 实现的。 多线程技术的主要优势在于充分利用 CPU的空闲时间片，用尽可能少的时间来对用户的要求作出响应，使系统整体运行效率得到一定的提高，增加 了 应用程序的灵活性。 10 多线程提高了系统响应能力及平滑的后台处理。 例如，一个字处理程序 (进程 )可以通过使用多线程来加强操作并简化与用户的交互。 该应用程序可以包含 3 个线程，第 1 个线程可以用于响应用户的键盘输入消息，将字符放入文档中；第2 个线程可以执行拼写检查及分页等后台操作 ； 第 3 个线程可以在后台将文档送到打印机打印。 互斥锁 临界资源是指在系统中有很多资源是多个 进程共享的资源中一次仅允许一个进程使用的那部分资源。 互斥 (间接相互制约关系 )指多个进程都想使用一个临界资源 ， 但是不能 同时 使用，于是只好一个进程用完了，才能给其他 的 进程用。 加锁法是对临界区加锁以实现互斥。 当某个进程进入临界区后 ， 就锁定临界区直到它退出临界区，其他进程要进入时， 需 要不断测试临界区是否被用着，直到临界区空着 时 才能进入。 在编程中，引入了对象互斥锁的概念，来保证共享数据操作的完整性。 每个对象都对应于一个可称为 “ 互斥锁 ” 的标记，这个标记用来保证在任一时刻，只能有一个线程访问该对象。 通常，互斥锁通过确 保一次只有一个线程执行代码的临界段来同步多个线程。 信号量 信号量 S为可用 临界资源 数量 ， 取值只允许为 “ 0” 和 “ 1” 的信号量称为二元信号量，主要用作互斥变量 (mutex)；取值允许为整数的信号量称为一般信号量 (semaphore)，主要用于进程间的同步问题。 )(/)( ssignalswait 操作 ： 最初是由芬兰学者 Dijkstra 于 1965年 提出的两个原子操作概念 ， 信号量除初始化外仅能通过这两个标准的原子操作 )(swait 和)(ssignal 来访问。 原子操作在执行时 是 不可中断的 ， 即当一个 进 程在修改某信号量时 ， 没有其他 进 程可同时对该信号量进行修改 ， 以解决进程间同步和互斥的问题。 )(swait 操作 ： 对某资源信号量 s 作 wait 操作 ， 表示申请资源 ， 可用资源数 s ；如果 0s ， 表示无资源可用 ， 本进程挂起 ， 变成等待资源 s 的“等待”状态。 )(ssignal 操作 ： 对某资源信号量 s 作 signal 操作 ， 表示释放资源 ， 可用资源数 1ss ； 如果 0s ， 表示有进程在等待该资源 ， 则释放该进程 ， 即将等待该资源 s 的首进程的状态变为“就绪”状态 ， 去等待 CPU继续运行。 根据对互斥信号量 mutex的不同设 置方式 ， 基于信号量的生产者 消费者问题算法 [7]有两种 ， (1) 生产者、消费者共 同使 用一个互斥信号量 mutex， 即生产者进程间、消费者进程间和生产者、消费者进程均互斥 ， 同一 时刻只 能有一个进程 11 访问缓冲区 ； (2)为生产者、消费者分别设置各自的互斥信号量，即生产者进程间使用 producerMutex进行互斥，消费者进程间使用 consumerMutex进行互斥，而生产者进程与消费者进程间不互斥。 一旦有可用的资源，两类进程就可以 同时访问缓冲区，同一时刻最多允许两个进程访问缓冲区，由于本文的算法中，借鉴的是第二种算法的思想，所以此处只演示算法 (2)的流程图。 图 5 生产者 消费者分别设置互斥量的流程图 由于 算法 2中 同一 时刻 最多允许两个进程访问缓冲区 ，所以 需要有两个指针ptop 、 pbottom 来分别指向生产者、消费者的下一个写入、读取位置。 4 基于人工蜂群算法的智力题求解 本文以“人工蜂群算法分析与实现”为题，在分析蜂群基本算法的基础上，将其在智力题的求解中实现。 本文算法中 采用多个线程并行技术模拟多只蜜蜂在同一时刻各司其职， 完成各自的任务。 通过考虑所选智力题的特征和结合操作系统方面的相关知识 (诸如进程、线程、多线程、信号量、互斥锁等 )提出数学模型，并在线程与线程之间添加一些限制条件来更好地模拟蜂群 ， 从而使多个智能性不高的线程也能像蜂群中不是很聪明的个体一样，通过一定的信息交流、协作共同完成 智力题的求解。 智力题求解问题概述 第一个答案是 b 的问题是哪一个。 12 (a)2。 (b) 3。 (c)4。 (d)5。 (e)6。