本文研究的是解决组合优化问题的算法及其应用，该课题是系统工程、运筹学、计算机科学的交叉学科。该学科中的许多问题都是迄今为止仍悬而未决的著名难题，具有极大的挑战性，诸如，旅行商问题、度约束最小树问题、二次分配问题、图着色问题等所谓的NP-难题。由于难计算是这类问题的固有性质，因此它们目前尚无法用有效算法精确求解，但这些问题在现实领域中有着许多广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。近年来，该领域中引入了一系列来自自然界的演化型算法，其思想吸收了许多看似无关的其它学科中的概念和方法，典型的有:遗传算法、模拟退火算法、禁忌搜索法、蚂蚁算法、粒子群算法、免疫算法等。　　本文在分析自然界以及人类各种竞争机制和决策原理的基础上，以演化博弈论和经济学中的竞争决策为基础，利用竞争造就优化和决策左右结果的特性，建立一个基于扩展式资源竞争的协调竞争决策模型，以该模型为基础设计了一个能求解各种组合优化问题的算法——竞争决策算法，并探讨了该算法在组合优化问题中的应用，为了提高各种算法的求解效率，在该算法的应用过程中，针对某些类型的问题，用数学推导和证明的方法得出一些能广泛应用的结论，这些结论，有些可以加快算法的执行速度和效果，有些可以评价优化算法所求解的效果，有些研究了问题的某些数学性质。在该算法的应用过程中完成了一套可运行于Windows95及其后续版本环境下的实用软件包。　　本文的具体内容包括:　　第一章概述了计算复杂性、演化类算法的几种主流思想及其研究现状。　　第二章介绍了博弈论的基本概念和发展历史，并以演化博弈论和经济学中的竞争决策为基础，利用竞争造就优化和决策左右结果的特性，建立一个基于扩展式资源竞争的协调竞争决策模型，在该模型的基础上设计竞争决策算法，给出了竞争决策算法的通用流程、特点、分类、主要概念及其数学描述、常用的竞争力函数、常用的决策函数、常用的初始状态以及常用的资源交换规则等。　　第三章主要讨论了经典TSP的求解方法，首先用数学推导和证明了一个求解TSP问题下界的快速算法，然后提供一个竞争决策算法来求解该问题，并求解了一系列的实际问题，获得了理想的效果。　　第四章讨论了若干扩展TSP的竞争决策算法求解及数学证明的算法，其中包括:瓶颈TSP的快速下界算法，基于快速下界算法的瓶颈TSP竞争决策算法、最小比率TSP竞争决策算法。通过大量实例的求解，取得了较好的效果。　　第五章对车辆路径(VRP)问题进行了求解，通过对大量的实例求解，获得了理想的效果，其中部分解好于当前公布的最好解。　　第六章中则对背包(KP)问题进行求解，首先通过数学推导和证明得出一个快速降阶算法，该降阶算法能够成批地确定一些一定在最优解中的物品，也能成批地确定一些一定不在最优解中的物品，然后在此基础上设计了一个求解0/1背包问题的竞争决策算法。　　第七章对度约束最小生成树这个难题设计了相应的竞争决策算法，通过大量试验求解并与其它算法作比较，发现竞争决策算法对于约束条件苛刻的问题实例来说，效果十分明显。　　总之，本文的研究从理论上提出了求解组合优化难题的新算法并给出一部分问题的数学性质及对应的算法，在应用上为复杂困难的系统优化问题提供了新的具有竞争力的求解算法，对一系列不同的组合优化问题设计了相应的求解策略并取得成功。