全球电子商务的不断发展和繁荣,创造了新的商业模式和新的商业机会。网上拍卖抓住了人类文明社会进步中的这一契机,一跃而起,成为电子商务活动中一种重要的商品交易方式。网上拍卖机制设计和算法研究已经得到了足够多的重视。在这些研究之中,组合拍卖是一个比较新的领域也是目前研究的热点。组合拍卖对具有关联价值的不同种类的物品同时拍卖,允许竞买人把多物品的任意组合作为“标的”进行投标,能够提高拍卖的效率和降低竞标人的风险。但竞胜标确定问题是一个NP难题,目前没有一种的算法能够有效地解决这一问题。因此,针对问题的特点,本文设计了一种嵌入优先适合启发式规则的改进极值优化算法,与传统算法相比,该算法具有实现方便,寻优效果好的优点。本文研究的主要内容有:一、系统地总结和分析传统拍卖理论的研究内容与方法。对网上多物品拍卖的机理研究、拍卖理论、组合拍卖问题及其机制设计的理论和相关的方法进行了综述。二、介绍了机制设计的理论与模型,并讨论了现有的各种组合拍卖机制的优点与缺点。由于现有的机制对于具有互补性物品的组合拍卖都存在各种不同的缺陷,所以提出了向上加价代理拍卖机制,这种机制流程简单,允许组合投标,也很好的解决了具有互补性物品的组合拍卖中可能会产生的信息披露等问题。三、在组合拍卖竞胜标问题的基础上结合网上拍卖的特点,在第一价格密封拍卖机制下建立了静态网上组合拍卖的模型。在向上加价代理机制下建立了价格动态的网上组合拍卖模型。四、提出了改进的极值优化算法求解模型:在算法中嵌入优先适合启发式构造可行解,并且极值优化算法的更新过程中不直接淘汰最差适应值的组合标,而将其放入整个“标的”队列的末位,作为优先适合启发式的输入。由于极值优化算法非平衡的特点,适于求解动态优化问题,所以本文提出了求解动态组合拍卖问题的极值优化算法,并讨论了在什么情况下采用动态算法比重复使用静态算法效果好。仿真结果显示,本文提出的极值优化算法对于静态和动态的组合拍卖问题都有良好的效果,具有广阔的应用前景。