基于动作空间求解二维矩形Packing 问题的高效算法

对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100％的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.     

基于动作空间的求解三维矩形装箱问题的穴度算法

基于拟人途径求解三维矩形装箱问题。在穴度算法的基础之上,通过定义当前格局下的极大空闲矩形空间即动作空间,使得穴度的定义既能反映其本质,同时又大能幅度地缩减计算量,从而使算法能在较短的时间内得出空间利用率较高的布局图案。试算了OR-Library中无方向约束的全部47个算例。实验结果表明,改进后的穴度算法得到的平均空间利用率为95. 24 %,将目前的最好结果提高了0.32%,且花费了更少的计算时间。     

一种求解二维矩形Packing问题的拟人型全局优化算法

针对二维矩形Packing问题,提出了基于占角动作的基本算法。以基本算法为基础,提出了三阶段优化的拟人型全局优化算法。在第一阶段生成初始布局。在第二阶段交替调用邻域搜索子程序和跳坑策略子程序对矩形块的优先级排序进行优化。邻域搜索采用交换式和插入式两种邻域结构,避免单一邻域结构的局限性。当搜索遇到局部最优解时,采用跳坑策略子程序跳出局部最优解,将搜索引向有希望的区域。在第三阶段调用优美度枚举子程序对占角动作的选择作进一步优化。提出了两条优度定理。对于六组benchmark测试用例的实验结果表明,算法的整体表现优于当前文献中的先进算法。针对矩形块方向固定的情形,算法对zdf6和zdf7两个问题实例得到了比已有文献记录更优的布局。     

基于穴度的三维时空优化问题的贪心调度算法

研究了基于二维矩形Packing的三维时空优化问题,即对给定的一个任意宽、高的大矩形框和有限个有连续加工时间要求的任意宽、高的小矩形块,如何安排每个小矩形块的入框时刻及其出框前每一时刻的位置和方向,使得所有小矩形块的总加工时间即总调度长度makespan最短。与经典布局问题的不同之处在于,各矩形块在框内可随时间的绵延而改变其位置和方向,从而能更充分地利用矩形框的空间。基于实角与实占角动作的定义,设计了求解其子问题二维矩形Packing问题的增强穴度算法。然后,每步迭代优先考虑剩余加工时间长的矩形块,提出了求解此问题的贪心穴度调度算法(caving-degree based greedy scheduling algorithm,CGSA)。作为比较,同时设计了矩形块在框内不可随时间移动的将时间简单类比为空间的对应Packing问题的调度算法CGSA′。对于实验中提出的满足非闸断模式的4个小型算例,它们在原问题上的最优调度长度为2,但若将时间简单地类比为空间,即矩形块放入框内后不可随时间移动其方位,则其最优调度长度为3。实验表明,算法CGSA在这4个非闸断算例上均得到了最优调度。进一步地研究出满足闸断模式的21组共210个自动生成算例,通过实验验证了算法CGSA的最优解的数目明显多于CGSA′,且CGSA的平均调度长度明显短于CGSA′。     

求解长方体Packing问题的高效算法

对典型的NP难度问题--著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语"金角银边草肚皮"的启发,并将它发展提高到"价值最高钻石穴",提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录.     

基于欧氏距离的矩形Packing问题的确定性启发式求解算法

使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.     

一种求解矩形块布局问题的拟物拟人算法

在VLSI工作中提出了矩形块布局问题，对这一问题，国内外学者提出了诸如模拟退火算法，遗传算法等求解算法。本文以人类上万年以来形成的经验为基础，利用“占角”和“聚类”两个拟物拟人的思想策略，提出了基于最大穴度优先的拟物拟人布局算法。甩本文提出的算法，对MCNC、GSRC两个典型测试算例的所有实例进行了实算测试，测试结果表明：计算所得布局结果的优度高，计算时间短。对MCNC和GSRC测试算例，除apte实例外，其它所有实例均得到了最优解，而计算时间都在10秒以内。与CBL算法、遗传算法和号称当今最好的CompaSS算法相比，本文算法所得结果的优度更高，计算时间更短。进一步的测试表明，本文提出的拟物拟人布局算法为当今的一种高效算法。     

求解二维矩形Packing问题的完备算法

对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关。通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了一种计算复杂度仅与待放块数相关的复杂度较低的完备算法。     

求解二维矩形Packing面积最小化问题的动态归约算法

二维矩形Packing 面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning 问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP 转化为求解一组二维矩形Packing 判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP 的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP 的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP 的最终算法.对15 个相关的RPAMP 算例(包括著名的MCNC 算例和GSRC 算例)进行了测试.更新了其中9 个算例的最好记录,另有2 个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%.     

基于动作空间的三维装箱问题的确定性高效率求解算法

三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚拟物体所对应的空间定义为动作空间,在动作空间内放入物体并使穴度的定义体现放入物体与动作空间的吻合程度;(2)在物体放入位置的选择上直接体现"金角银边草肚皮"的思想,每一步只选择最靠近箱子边缘的一个动作空间来装载物体;(3)结合捆绑策略,将形状大小相同的物体捆绑为一个较大的矩形块进行放入,对捆绑块形状大小的选择为在不超出动作空间的前提下尽量用物体填满该空间的两至三个维度.实验结果表明,改进后的穴度算法在付出很少的开销代价的情况下显著地提高了箱子的填充率.     

Call for Papers The 6^th International Conference on Grid and Cooperative Computing

Recent years have seen rapid advances in various grid-related technologies, middleware, and applications. The GCC conference has become one of the largest scientific events worldwide in grid and cooperative computing. The 6th international conference on grid and cooperative computing (GCC2007) Sponsored by China Computer Federation (CCF),Institute of Computing Technology, Chinese Academy of Sciences (ICT) and Xinjiang University ,and in Cooperation with IEEE Computer Soceity ,is to be held from August 16 to 18, 2007 in Urumchi, Xinjiang, China.     

Only connect: teaching, technology and telesis

Abstract This paper describes an approach to the design of interactive multimedia materials being developed in a European Community project. The developmental process is seen as a dialogue between technologists and teachers. This dialogue is often problematic because of the differences in training, experience and culture between them. Conditions needed for fruitful dialogue are described and the generic model for learning design used in the project is explained.     

法律信息库系统

本文分析了法律数据库的结构和特点，介绍了采用面向对象设计方法和超文本数据库技术开发和实现法律信息库系统将作为重要网络资源之一为不同用户进行法律咨询服务。     

International Journal of Automation and Computing Table of Contents

正~~     

Information for authors

正SCIENCE CHINA Information Sciences(Sci China Inf Sci),cosponsored by the Chinese Academy of Sciences and the National Natural Science Foundation of China,and published by Science China Press,is committed to publishing highquality,original results of both basic and applied research in all areas of information sciences,including computer science and technology;systems science,control science and engineering(published in Issues with odd numbers);information and communication engineering;electronic science and technology(published in Issues with even numbers).Sci China Inf Sci is published monthly in both print and electronic forms.It is indexed by Academic OneFile,Astrophysics Data System(ADS),CSA,Cabells,Current Contents/Engineering,Computing and Technology,DBLP,Digital Mathematics Registry,Earthquake Engineering Abstracts,Engineering Index,Engineered Materials Abstracts,Gale,Google,INSPEC,Journal Citation Reports/Science Edition,Mathematical Reviews,OCLC,ProQuest,SCOPUS,Science Citation Index Expanded,Summon by Serial Solutions,VINITI,Zentralblatt MATH.     

Erratum to: Fast global kernel fuzzy c-means clustering algorithm for consonant/vowel segmentation of speech signal

正Erratum to:J Zhejiang Univ-Sci C(ComputElectron)2014 15(7):551-563doi:10.1631/jzus.C1300320The original version of this article unfortunately contained mistakes.Algorithm 6 should be as follows:Algorithm 6 FGKFCM-F clustering Input:(1)X={x_1,x_2,…,x_N},,x_iR~d,i=1,2,…,N,the dataset;(2)C,1C≤N,the number of clusters;(3)ε0,the stopping criterion;     

Journal of Zhejiang University-SCIENCE C (Computers & Electronics) Total contents

正~~     

磨机负荷专家控制系统设计及仿真研究

磨矿过程的大滞后和时变性等特点,致使对磨机负荷的最佳工作点很难进行稳定、高效的控制,针对以上情况,借鉴生物界的免疫反馈原理和遗传算法,利用模糊控制可以有效地实现对非线性、纯滞后、复杂的对象进行控制的优点,并结合PID与自寻优方法,设计出磨机负荷专家控制系统,用VB编写OPC客户端及控制程序,实现对磨机负荷的动态优化控制;试验结果表明,文章提出的控制策略能够增强系统的稳定性,且在干扰存在的情况下也能很好的跟随系统的参数变化,在提高磨机台时产量的同时增加了矿厂的经济效益.     

基于人工蜂群的无线传感器网络能耗均衡算法

由于无线传感器网络中的节点链路状况、数据传输能耗及节点剩余能量的限制,造成网络中部分感知节点寿命缩短,影响网络生存周期,提出了一种基于人工蜂群算法的WSNs能耗均衡算法,优化网络能耗均衡,从而提高网络寿命;文章给出了网络能耗相应的数学模型及优化求解算法,介绍人工蜂群算法的寻找食物过程,阐述了人工蜂群算法在网络能耗均衡方面的实现步骤;通过实验仿真证明,文章提到的算法与LEACH分簇算法、蚁群优化算法相比,具有更好的能耗和负载均衡能量、丢包率和时延性,有效地提高了网络生存周期.