倒数第三篇: 第 11 章  作 业 调 度
倒数第二篇:11.2  JSP 的遗传算法
主页
第一篇:《用 于 最 优 化 的 计 算 智 能》
第二篇: 第 1 章  引  言
文章列表

11.3  仿真结果

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

我们对上面一节讨论的GA用不同规模的JSP 进行了仿真,并将其结果与传统调度

程序RANDOM,MOPNR,MWKR-P,MWKR/P,SPT,以及LWKR 等进行了比较。

表11.1~11.2是GA与传统调度程序的完成时间的对比。这里所用的交叉概率为

0.8,突变概率为0.2,且群体大小为80 (作业个数)。表11.1给出的是对于8个不同的

10/10问题GA 在1000代以上所得的最好调度与传统程序所得调度的比较。表11.2给

出的是对于8个不同的100/50问题GA在1000代以上所得的最好调度与传统程序所得

调度的比较。即使对于实际问题来说,100/50问题的规模也是足够大的了。

表11.1  10/10问题的完成时间

GA RANDOM MOPNR MWKR-P MWKR/P SPT MWKR LWKR

1 64 66 69 83 88 70 67 86 v

2 71 76 80 84 73 79 83 89 v

3 64 66 74 74 70 74 75 91 v

4 73 77 83 87 86 81 84 99 v

5 83 86 97 98 114 113 105 114 v

6 83 83 85 96 96 98 84 100 v

7 89 97 99 114 123 120 105 134 v

8 87 90 102 116 116 119 97 102 ^

表11.2  100/50问题的完成时间

GA RANDOM MOPNR MWKR-P MWKR/P SPT MWKR LWKR

1 549 574 537 614 727 607 541 718 ^

2 550 579 557 672 691 616 558 708 ^

3 563 591 565 604 663 625 555 704 ^

4 548 567 539 640 685 603 551 669 ^

5 547 576 553 617 679 652 549 694 ^

6 543 572 544 650 664 603 541 702 ^

#第115页-

续表

GA RANDOM MOPNR MWKR-P MWKR/P SPT MWKR LWKR

7 552 574 554 610 661 606 562 734 ^

8 553 587 555 622 692 641 566 712 ^

从这些比较可以看出,GA所得结果相当不错。对于10/10问题,GA 的结果总是最好

的;对于100/50问题,GA 的结果也在最好之列。相对于所有其它程序的平均水平,GA 总

体上将10/10问题的解答改进了17%,并将100/50问题改进了14%。同时可以看到,传

统程序的表现随测试问题不同有很大起伏,而GA在所有测试问题上的表现则相对稳定。

至于运行时间,GA 比多数传统程序的计算时间要长。这是因为GA 是一个迭代算

法,而其它算法则为一次性的。不过,GA在本质上是并行的,并可在并行处理情况下获得

很高效率。

11.4  习题

11.1  利用11.2.3节介绍的遗传算法和OX操作进行仿真,求解JSP。

11.2  利用遗传算法和PMX操作进行仿真,求解JSP。

11.3  利用遗传算法和CX操作进行仿真,求解JSP。

11.4  比较OX,PMX和CX求解JSP 的性能。

#第116页-

参 考 文 献

[1] Aazhang, B., B.P. Paris and G.C. Orsak,“Neural networks for multiuser detection in code-

divisionmultiple-access communications,”IEEE Trans.on Communications, vol. 40, no. 7, July

1992,pp.1212—1222.

[2] Aarts,E.and J.Korst,Simulated AnnealingandBoltzmann Machines.New York: Wiley&Sons,

1989.

[3] Aarts, E. H.L. and J.H.M. Korst,“Boltzmann machines for travelling salesman problems,”

EuropeanJournalof Operational Research,vol.39,Issue 1,March 6,1989,pp.79—95.

[4] Aarts,E.andP.J.M.van Laarhoven,“A new polynomialtime cooling schedule,”Proc.IEEE Int.

Conf.on Computer-AidedDesign,SantaClara,CA,November 1985,pp.206—208.

[5] Abramson,D.,“Constructing school timetables using simulated annealing sequential and parallel

algorithms,”Management Science,vol.37,no.1,January1991,pp.98—103.

[6] Abrishamkar,F.and Z.Siveski,“PCS global mobile satellites,”IEEE Communications Magazine,

vol.34,no.9,September 1996.

[7] T. L. Adams et al.,“A comparison of list schedules for parallel processing systems,” %

CommunicationsofACM,vol.17,December 1974,pp.685—690.

[8] Abu-Mostafa,Y.S.andJ.St.Jacques,“InformationcapacityoftheHopfieldmodel,”IEEE Trans.on

InformationTheory,vol.31,July1985,pp.461—464.

[9] Agrawal,A.,N.Ansari and E.S.H.Hou,“Evolutionary programming for fast and robust point

pattern matching,”Proc.1994 IEEE Conference onNeural Networks,Orlando,FL,June 28—July

2,1994,pp.1777—1782.

[10] Aho,A.V.,J.E.Hopcroft andJ.D.Ullman,The Design and Analysis of Computer Algorithms. #

New York:AddisonWesley,1974.

[11] Aiyer,S.V.B.,M.Niranjan and F.Fallside,“A theoretical investigation intotheperformance of

theHopfieldmodel,”IEEE Trans.onNeuralNetworks,vol.1,June1990,pp.204—215.

[12] Akiyama,Y.,A.Yamashita,M.Kajiura and H.Aiso,“Combinatorial optimization with Gaussian

machines,”Proc.InternationalJointConferenceon NeuralNetworks,Washington,D.C,1989,pp.

I:533—540.

[13] Anderson,J.A. andE. Rosenfeld,(eds.),Neurocomputing:Foundations of Research.Cambridge,

MA:MIT Press,1988.

[14] Anisimov, V.Y.,“Parameter estimation in the case of fuzzy information on the observation 3

conditions,”TelecommunicationsandRadioEngineering,vol.44,no.5,May1989,pp.86—88.

[15] Ansari,N.,A.Arulambalam andS.Balasekar,“Traffic management of asatellite communication )

network using stochasticoptimization,”IEEE Trans.on Neural Networks,vol.7,May 1996,pp.

732—744.

[16] Ansari,N.,M.Chen and E.S.H.Hou,“CHAPTER 13: A genetic algorithm for point pattern '

matching,”in Dynamic,Genetic and Chaotic Programming—The Sixth-Generation (B.Soucek

#第117页-

ed.),pp.353—371,New York: Wiley&Sons,1992.

[17] Ansari,N.andE.J.Delp,“Partialshaperecognition: alandmarkbasedapproach,”IEEE Trans.on

PatternAnalysis andMachineIntelligence,vol.12,no.5,May1990,pp.470—483.

[18] Ansari,N.,E.S.H.HouandA.Agrawal,“Point patternmatchingbysimulatedannealing,”Proc.

1993IEEE RegionalConferenceonControlSystems,Newark,NJ,August 13—14,1993,pp.215—

218.

[ 19] Ansari, N., E. S. H. Hou and Y. Yu,“A new method to optimize the satellite broadcasting C

schedules usingthemean fieldannealingof a Hopfieldneural network,”IEEE Trans.on Neural

Networks,vol.6,no.2,March1995,pp.470—483.

[20] Ansari,N.andK.Li,“LandmarkbasedshaperecognitionbyamodifiedHopfieldneuralnetwork- ,”

PatternRecognition,vol.26,no.4,April1993,pp.531—542.

[21] Ansari, N. and X. Liu,“Recognizing partially occluded objects by a bidirectional associative B

memory,”OpticalEngineering,vol.32,no.7,July1993,pp.1539—1548.

[22] Ansari,N.,R.Sarasa and G.Wang,“An efficient annealingalgorithm for global optimization in

Boltzmannmachines,”AppliedIntelligence,vol. 3,1993,pp.177—192.

[23] Banerjee,P.,M.H. Jones and J. S. Sargent,“Parallel simulated annealing algorithms for cell ,

placement onhypercubemultiprocessors,”IEEE Trans.onParallel andDistributedSystems,vol.

1,no.1,January1990,pp. 91—106.

[24] Baram,Y.,“On thecapacityofternaryHopfieldnetworks,”IEEE Trans.on InformationTheory,

vol.37,May1991,pp.528—534.

[25] Baram, Y.,“Encoding unique global minima in nested neural networks,”IEEE Trans. on C

InformationTheory,vol.37,July1991,pp.1158—1162.

[26] Barr,A.and E.A.Feigenbaum,The Handbook of Artificial Intelligence,vol.I.Los Altos,CA: 5

Kaufmann,1981.

[27] Bartle,R.G.,TheElements of RealAnalysis,2ndEdition.New York: Wiley&Sons,1976.

[28] Basso, A.and M.Kunt,“Autoassociative neural networks for image compression,”European 2

Trans.onTelecommunications,vol.3,no.6,November 1992,pp.593—598.

[29] Battiti,R.andG.Tecchiolli, Simulatedannealingandtabusearchinthelongrun: acomparisonon

QAP tasks,”Computers andMathematics with Applications,vol.28,no.6,1994,pp.1—8.

[30] Belew,R.K.and L.B.Booker,(eds.),Proc.of the Fourth International Conference on Genetic ¥

Algorithms.SanMateo,CA: MorganKaufmannPublishers,Inc.,1991.

[31] Biegel,J.E. andJ.J.Davern,“Geneticalgorithms andjobshopscheduling,”Computers industrial

Engineering,vol.19,nos.1—4,1990,pp.81—91.

[32] Bilbro,G.L.,W.E.Snyder and J.W.Gault,“Mean fieldannealing: a formalism for constructing

GNC-likealgorithms,”IEEE Trans.onNeuralNetworks,vol.3,no.1,1992,pp.131—138.

[33] Boissin,N.andJ.-L.Lutton,“A parallelsimulated annealingalgorithm,”ParallelComputing,vol.

19,no.8,August 1993,pp.859—872.

[34] Bourret,P.,S.GoodallandM.Samuelides, Optimalschedulingcompetitiveactivation: application

to the satellite antennas scheduling problem,”Proc.IJCNN’89,Washington, D. C., 1989, pp.

I565—572.

[35] Bourret,P.,F.Rem and S.Goodall,“A special purpose neural network for scheduling satellite )

broadcastingtimes,”Proc.IJCNN’90,Washington,D.C.,1990,pp.II535—538.

#第118页-

[36] Chao,D.Y.and D.T.Wang,“Enhancement of memorycapacityof neural networks,”Proc.1992

IEEE/RSJ Intl.Conf. onIntelligent Robots andSystems,Raleigh,NC,July7—10,1992,pp.519—

526.

[37] Chang,C.and C.Wu,“Optimal frame pattern design of a TDMA mobile communication system

usinga simulatedannealingalgorithm,”IEEE Trans.onVehicular Technology,vol.42,May1993,

pp.205—211.

[38] Chang, P.-R., and B.-C. Wang,“Adaptive decision feedback equalization for digital satellite =

channels usingmultilayer neuralnetworks,”IEEE JournalonSelectedAreasinCommunications,

vol.13,no.2,February1995,pp.316—324.

[39] Chen,C.L.,C.S.G.Lee,and E.S.H.Hou,“Efficient scheduling algorithms for robot inverse )

dynamics computation on a multiprocessor system,”IEEE Trans. on Systems, Man and

Cybernetics,vol.18,no.5,December 1988,pp.729—743.

[40] Chen,S.,B.Mulgrew andP.M.Grant, A clusteringtechniquefor digitalcommunicationschannel

equalizationusingradialbasisfunctionnetworks,”IEEETrans.onNeuralNetworks,vol.4,no.4,

July1993,pp.570—579.

[41] Chen,X.and I.M.Leslie,“Neural adaptive congestion control for broadband ATM networks,” ¥

IEE Proc.I,Communications,Speech,andVision,vol.139,no.3,pp.233—240.

[42] Chou, L.-D. and J.-L. C. Wu,“Parameter adjustment using neural-network-based genetic F

algorithms for guaranteed QOS in ATM networks,”IEICE Trans.on Communications,vol.78,

no.4,April1995,pp.572—579.

[43] Cleveland,G.A. andS.F.Smith,“Usinggeneticalgorithms toscheduleflow shoprelease,”Proc.

3rdInt.Conf.onGeneticAlgorithmsandtheir Applications,Arling,VA,1989,pp.160—169.

[44] Conway,R.W.,W.L.Maxwell,and L.W.Miller,(eds.),Theory of Scheduling.Reading,MA: "

Addison-Wesley,1967.

[45] Cook,J., Themean-fieldtheoryof a Q-stateneural network model,”Journalof Physics A,vol. "

22,no.12,June21,1989,pp.2057—2068.

[46] Cook,S.A.,“The complexity of theorem-proving procedures,”Proc.3rd Ann.ACM Symp.on -

TheoryofComputing,ACM,1971,pp.151—158.

[47] Cooper,P.G.,“Neural networks enable radiowave propagation modeling,”Signal,vol.47,no.6,

February1993,pp.29—31.

[48] Davenport Jr.,W.B.,ProbabilityandRandomProcess.NewYork: McGraw-Hill,1970.

[49] Davis, L.,“Job shop scheduling with genetic algorithms,”Proc. of the First International D

Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University,

Pittsburgh,PA,July24—26,1985,pp.136—140.

[50] Davis,L.,“Applying adaptive algorithm to epistatic domains,”Proc.of the International Joint &

ConferenceonArtificial Intelligence,1985,pp.162—164.

[51] Duque-Anton,M.,D.KunzandB.Ruber,“Channel assignment for cellular radiousingsimulated

annealing,”IEEE Trans.onVehicular Technology,vol.42,no.1,February1993,pp.14—21.

[52] Fischer,M.J.andT.C.Harris,“A modelfor evaluating the performanceof an integratedcircuit )

and packet-switched multiplex structure,”IEEE Trans.on Communications,vol. 24, February

1976,pp.195—202.

[53] Foo,Y.P.S.andY.Takefuji, Stochasticneural networks for solving job-shopscheduling,”Proc.

#第119页-

IEEE IJCNN 88,1988,pp.275—290.

[54] Foo, Y. P. S. and Y. Takefuji,“Integer-neural programming neural networks for job-shop D

scheduling,”Proc.IEEE IJCNN 88,1988,pp.341-348.

[55] Friesz,T.,H. J. Cho and J.N. Mehta,“Simulated annealing approach to the network disign .

problem with variational inequality constraints,”Transportation Science,vol.26,no.1,February

1992,pp.18—26.

[56] Fu,Y.and P.W.Anderson,“Application of statistical mechanics to NP-complete problems in 4

combinatorialoptimization,”JournalofPhysics A,vol.A19,1986,pp.1605—1620.

[57] Garey,M.R.and D.S.Johnson,Computers and Intractability.New York: W.H.Freeman and (

Company,1979.

[58] Gelfand, S.B., Analysis of Simulated Annealing for Optimization,Massachusetts Institute of 1

Technology,Ph.D.Dissertation,1987.

[59] Geman,S.and D.Geman,“Stochastic relaxation,Gibbs distribution and Baysian restoration in 5

images,”IEEE Trans.on Pattern Analysis and Machine Intelligence,vol.6,November 1984,pp.

721—741.

[60] Gelfand,S.B. and S. K. Mitter,“Weak convergence of Markov chain sampling methods and 3

annealingalgorithms todiffusion,”Journal of OptimizationTheoryand Applications,vol.68,no.

3,March 1991,pp.483—498.

[61] Gidas,B.,“NonstationaryMarkovchains andconvergenceof the annealingalgorithm,”Journal of

StatisticalPhysics,vol.39,1985,pp.73—131.

[62] Glauber,R.J.,“Time-dependent statistics of theIsing model,”Journal of MathematicalPhysics,

vol.4,1963,pp.294—307.

[63] Goffe, W. L., G. D. Ferrier and J. Rogers,“Simulated annealing: an initial application in >

econometrics,”ComputationalEconomics,vol.5,no.2,May1992,pp.133—146.

[64] Goldberg,D.E.,GeneticAlgorithms inSearch,Optimization,and MachineLearning.New York: &

AddisonWesley,1989.

[65] Goldberg,D.E.,and R.Lingle,“Alleles,loci,and the traveling salesman problem,”Proc.of an (

InternationalConferenceonGeneticAlgorithms andTheir Applications,1985,pp.154—159.

[66] Gonzalez,M.J.,“Deterministicprocessor scheduling,”ComputingSurveys,vol.9,no.3,September

1977,pp.173—204.

[67] Grefenstette, J. J., (ed.), Genetic Algorithms and Their Applications: Proc. of the Second E

International Conference on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum Assoc.,

Publishers,1987.

[68] Guo,H.,M.ZuckermannandR.Harris,“A fast algorithm simulated annealing,”Physica Scripta, "

vol.38,1991,pp.40.

[69] Habib,I.W.,A.A.Tarraf and T.N.Saadawi,“Intelligent traffic control for ATM broadband /

networks,”IEEECommunicationsMagazine,vol.33,no.10,October 1995,pp.76—82.

[70] Hajek,B.,“Cooling schedules for optimal annealing,”Mathematics of Operations Research,vol. ,

13,1988,pp.311—329.

[71] Handley,S.,“Thegeneticplanner: theautomaticgenerationofplansfor amobilerobotviagenetic

programming,”Proc.of8thIEEE InternationalSymposium onIntelligent Control,1993.

[72] Harrington,E.A.,“Voice/data integration using circuit switched networks,”IEEE Trans.on =

#第120页-

Communications,vol.28,June1980,pp.781—793.

[73] Hart,P.E.,N.J.Nilsson,B.Raphael, A formalbasis for theheuristicdeterminationof minimum

cost paths,”IEEE Trans.onSSC,vol.SCC-4,1968,pp.100—107.

[74] Hattori,S.,J.Mizusawa and K.Murakami,“User programmability of communication network 6

serviceswithassociative-memoryneuralnetworks,”Electronics &Communications inJapan,Part

1.,vol.75,no.11,November 1992,pp.1—13.

[75] Haykin,S.,NeuralNetworks: A ComprehensiveFoundation.New York: Macmillan,1994.

[76] Hellstrom, B. and L. Kanal,“Asymmetric mean-field neural networks for multiprocessor T

scheduling,”NeuralNetworks,vol.5,1992,pp.671—686.

[77] Hinton,G.E.and T.J.Sejnowski,“Learning and relearning in Boltzmann machines,”in Parallel 0

DistributedProcessing,Volume 1(Rumelhart,McClelland,and the PDP Group ed.),Cambridge,

MA: MIT Press,pp.282—317.

[78] Hiramatsu,A., Integrationof ATMcalladmissioncontrolandlinkcapacitycontrolof distributed

neural networks,”IEEE Journal on Selected Areas in Communications,vol.9,no.7,September

1991,pp.1131—1138.

[79] Hiramatsu, A.,“Training techniques for neural network applications in ATM,”IEEE c

Communications Magazine,vol.33,no.10,October 1995,pp.58—67.

[80] Hiriyannaiah,H.P.,G.L.Bilbroand W.E.Snyder,“Restoration of piecewise-constant images by

meanfieldannealing- ,”JournaloftheOpticalSocietyofAmerica,vol.6,no.12,December 1989,pp.

1901—1912.

[81] Hoitimt,D.J.,P.B.Luh,andK.R.Pattiati, Job shop scheduling,”First InternationalConference

onAutomationTechnology,Taipei,Taiwan,July1990,pp.565—574.

[82] Hoitimt, D. J., P. B. Luh, and K. R. Pattiati,“A practical approach to job-shop scheduling >

problems,”IEEE Transaction on Robotics andAutomation,vol.9,no.1,February 1993,pp.1—

13.

[83] Holland,J.,AdaptationinNaturalandArtificialSystems.AnnArbor: TheUniversityofMichigan

Press,1975.

[84] Hopfield,J.J.,“Neural networks and physical systems with emergent collective computational /

abilities,”Proc.of the National Academy of Sciences of the U.S.A.,vol. 79,April 1982,pp.

2554—2558.

[85] Hopfield,J.J., Neurons with gradedresponsehave collective computational properties likethose

of two-state neurons,”Proc.of the National Academy of Sciences of the U.S.A.,vol.81,May

1984,pp.3088—3092.

[86] Hopfield,J.J.and T.W.Tank,“Neural computation of decisions in optimization problems,” 2

BiologicalCybernetics,vol.52,1985,pp.141—152.

[87] Hou,E.S.H.,N.AnsariandH.Ren,“A geneticalgorithm for multiprocessor scheduling,”IEEE %

Trans.ParallelandDistributedSystems,vol.5,no.2,February1994,pp.110—111.

[88] Hou,E.andD.Liu. N/M job-shopschedulingwithageneticalgorithm,”inIntellient Automation

andSoft Computing: Trends in Research,Development andApplications(M.Jamshildied.),New

Mexico: TSI Press,vol.1,1994,pp.511—516.

[89] Hsu,J.C.and A.U.Meyer,Modern Control Principles and Applications.New York: McGraw- !

Hill,1968.

#第121页-

[90] Huttenlocker, D. P. and S. Ullman,“Object recognition using alignment,”Proc. IEEE First I

InternationalConferenceonComputer Vision,London,England,1987,pp.102—111.

[91] Hwang,K.andF.A.Briggs,Computer ArchitectureandParallelProcessing.New York: McGraw

Hill,1984.

[92] Ingber,L.,“Veryfastsimulatedre-annealing,”MathematicalandComputer Modeling,vol.12,no.

8,1989,pp.967—973.

[93] Jeong,C.S.andM.H.Kim,“Fast parallelsimulatedannealingfor travelingsalesman problem on "

SMDmachines with linear interconnections,”Parallel Computing,vol.17,no.2/3,June 1991,pp.

221—228.

[ 94] Karp, R. M.,“Reducibility among combinatorial problems,”in Complexity of Computer \

Computations(R.E. Miller andJ.W.Thatcher eds.),New York: Plenum Press,1972.

[95] Kasahara,H.andS.Narita,“Practical multiprocessing schedulingalgorithms for efficient parallel

processing,”IEEE Trans.onComputers,vol.C-33,no.11,November 1984,pp.1023—1029.

[96] Kasahara, H. and S. Narita,“Parallel processing of robot-arm control computation on a J

multimicroprocessor system,”IEEE Journal of Robotics andAutomation,vol.RA-1,no.2,June

1985,pp.104—113.

[97] Kim,S.-S.andC.-M.Kyung, Moduleorientationalgorithmusingreconstructionofnetsandmean

fieldannealing,”Electronics letters,vol.27,no.13,June20,1991,pp.1198—1199.

[98] Kirkpatrick,S.,C.D.Gelatt Jr.andM.P.Vecchi, Optimizationbysimulatedannealing,”Science,

vol.220,1983,pp.671—680.

[99] Lenstra, J. K., A. H. G. Rinnooy Kan, and P. Bruckner,“Complexity of machine scheduling 7

problems,”Annals ofDiscreteMathematics,vol.7,1977,pp.343—362.

[100] Leong,H.W.,D.G.Wong and C.L.Liu,“A simulated annealing channel router,”Proc.IEEE N

internationalConferenceonComputer-AidedDesign,SantaClara,CA,November 1985,pp.226—

229.

[101] Lin,F.T.,C.Y.Kaoand C.C Hsu,“Applying the genetic approach to simulated annealing in M

solvingsomeNP-hardproblems,”IEEE Trans.on Systems,Man,andCybernetics,vol.23,no.6,

November 1993,pp.1752—1767.

[102] Lin,S.,“Computer solutions of thetravelingsalesmanproblem,”BellSystem TechnicalJournal, E

vol.44,1965,pp.2245—2269.

[103] Liepin,G.E.and M.R.Hilliard,“Greedy genetics,”Proc.2nd Int.Conf.on Genetics Algorithms D

andTheir Applications,Cambridge,MA,1987,pp.90—99.

[104] Lockwood,C.andT.Moore,“Harvest scheduling with spatial constraints: asimulatedannealing C

approach,”CanadianJournalof ForestResearch,vol.23,no.3,March1993,pp.468—478.

[105] Luenberger,D.G.,Linear andNonlinear Programming.Reading,MA: AddisonWesley,1984. E[106] Malek,M.,M.Guruswamy and M.Pandya,“Serial and parallel simulated annealing and tabu [

search algorithms for thetravelingsalesman problem,”Annals of Operations Research,vol.21,

no.1/4,November 1989,pp.59—84.

[107] McEliece,R.J.,E.C.Posner,E.R.RodemichandS.S. Venkatesh,“ThecapacityoftheHopfield E

associativememory,”IEEE Trans.onInformationTheory,vol.33,July1985,pp.461—482.

[108] Metropolis,N.A.,A.Rosenbluth,M.Rosenbluth,A.Teller and E.Teller,“Equation of state Z

calculations by fast computingmachines,”Journalof Chemical Physics,vol.21,1953,pp.1087—

#第122页-

1092.

[ 109] Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs. Berlin

Heidelberg: Springer-Verlag,1992.

[110] Miller,R.E.and J.W.Thatcher,Complexity of Computer Computations.New York: Plenum V

Press,1972.

[111] Morris,R.J.T. and B.Samadi,“Neural network control of communications systems,”IEEE Z

Trans.onNeuralNetworks,vol.5,no.4,July1994,639—650.

[112] Nakano,R.andT.Yamada,“Conventional geneticalgorithms for job shop problems,”Proc.4th W

Int.Conf.OnGenetics Algorithms andTheir Applications,San Diego,CA,1991,pp.474—479.

[113] Ndousse,T.D. Fuzzyneuralcontrolofvoicecells inATM networks,”IEEEJournalonSelected E

Areas inCommunications,vol.12,no.9,December 1994,pp.1488—1495.

[114] Neves,J.E.,M.J.Leitao and L.B.Almeida,“Neural networks in BISDN flow control: ATM N

trafficpredictionor network modeling?”IEEE communications magazine,vol.33,no.10,October

1995,pp.50—57.

[115] Nilar,S.H.,“Applications of the simulated annealing method to intermolecular interactions,” V

JournalofComputationalChemistry,vol.12,no.8,October 1991,pp.1008—1013.

[116] Nilsson,N.J.,Learning Machines: Foundations of Trainable Pattern Classifiers.New York: ^

McGraw-Hill,1965;also republished as The Mathematical Foundations of Learning Machines.

SanMateo,CA: MorganKaufmannPublishers,1990.

[117] Nilsson,N.J.,Problem-solving Methods in Artificial Intelligence.New York: McGraw-Hill, b

1971.

[118] Nilsson,N.J.,Principles of Artificial Intelligence.Palo Alto,CA: Tioga Publishing Company, N

1980.

[119] Nobakht,R.A.,S.H.Ardalan and D.E.Van denBout,“Adaptivefilteringof nonlinear systems P

withmemorybyquantizedmean fieldannealing,”IEEE Trans.on Signal Processing,vol.41,no.

2,February1993,pp.913—925.

[120] Nobakht,R. A.,D. E. Van den Bout and J.K. Townsend,“Optimization of transmitter and g

receiver filters for digitalcommunicationsystems using mean fieldannealing,”IEEE Journalon

SelectedAreasinCommunications,vol.8,no.8,October 1990,pp.1472—1480.

[121] Nordstrom,E.,J.Carlstrom and L.Asplund,“Neural networks for adaptive traffic control in [

ATM networks,”IEEECommunicationsMagazine,vol.33,no.10,October 1995,pp.43—49.

[122] Oliver,I.M.,D.J.Smith,J.R.C.Holland,“A studyof permutation crossover operators on the W

traveling salesman problem,”Proc. of the Second International Conference on Genetic

Algorithms,Cambridge,MA,July28—31,1987,pp.224—230.

[123] Otten,R.H.J.M.andL.P.P.P.van Ginneken,The Annealing Algorithm.Boston,MA: Kluwer K

AcademicPublishers,1989.

[124] Ozcelik,T.,J.C.BraileanandA.Katsaggelos,“Imageandvideocompressionalgorithmsbasedon F

recoverytechniques usingmeanfieldannealing,”Proc.of theIEEE,vol.83,no.2,Feb.1995,pp.

304—316.

[125] Papadimitriou C.and K.Steiglitz,CombinatorialOptimization: Algorithms and Complexity.New K

York: PrenticeHall,Inc.,1982.

[ 126] Park, Y.-K. and G. Lee,“Applications of Neural Networks in high-speed communication

#第123页-

networks,”IEEE Communications Magazine,vol.33,no.10,October 1995,pp.68—75.

[127] Pearl,J.,Heuristics: Intelligent Search Strategies for Computer Problem Solving.NY: Addison- H

WesleyPublishingCompany,1984.

[128] Peterson,C.and J.R.Anderson,“A mean fieldtheorylearningalgorithm for neuralnetworks,” P

ComplexSystems,vol.1,1987,pp.995—1019.

[129] C.Peterson and J.R.Anderson,“Neural networks and NP-complete optimization problems: a U

performancestudyonthegraphbisectionproblem,”ComplexSystems,vol.2,1988,pp.59—89.

[130] Peterson,C.and J.R.Anderson,“Applications of mean field theory neural networks,”Dept.of N

TheoreticalPhysics,TechnicalReport CS-1153,Univ.ofLund,August 1989,pp.1—27.

[131] Peterson,C.and E.Hartman,“Explorations ofthemeanfieldtheorylearningalgorithm,”Neural L

Networks,vol.2,August 1989,pp.475—494.

[132] Peterson,C.and B.Soderberg,“A new method for mapping optimization problems ontoneural O

networks,”InternationalJournalofNeuralSystems,vol.1,no.1,1989,pp.3—22.

[133] Pospichal,J.and V.Kvasnicka,“Fast evaluation of chemical distrane by simulatedannealing- k

algorithm,”Journal of Chemical Information and Computer Science,vol.33,no. 6,November

1993,pp.879—885.

[134] Pritchard, W. L., H. G. Suyderhoud and R. A. Nelson, Satellite Communication Systems {

Engineering,2ndEdition.EnglewoodCliffs,NJ: PrenticeHall,1993.

[135] Pratt,W.K.,Digital ImageProcessing,2ndEdition.New York: Wiley&Sons,1991. E[136] Ramamoorthy,C.V.et al.,“Optimal scheduling strategies in a multiprocessor system,”IEEE Y

Trans.Computers,vol.C-21,February1972,pp.137—146.

[137] Reddi,S.S.and C.V.Ramamoorthy,“On the folw-shop sequencing problem with no waiting Z

process,”OperationalResearchQuarterly,vol.23,no.3,1972,pp.323—331.

[138] Rong,L.and L.Ze-min, Parameters rules of theHopfield/Tank model on solving TSP,”Proc. S

1992IEEE ConferenceonNeuralNetworks,Baltimore,MD,June7—11,1992,pp.IV.492—497.

[139] Rose,C.,“Low mean internodal distance network topologies and simulated annealing,”IEEE ]

Trans.onCommunications,vol.40,no.8,August 1992,pp.1319—1326.

[140] Rosenfeld,A.,“Image Analysis and Computer Vision: 1993,”Computer Vision,Graphics and Z

Imageprocessing,vol.59,no.3,May1994,pp.367—405.

[141] Rosenfeld, A.,“Image Analysis and Computer Vision: 1994,”Computer Vision and Image n

Understanding,vol.62,no.1,July1995,pp.90—133.

[142] Rosenfeld, A.,“Image Analysis and Computer Vision: 1995,”Computer Vision and Image n

Understanding,vol.63,no.3,May1996,pp.568—627.

[143] Schaffer,J.D.,Proc.of the ThirdInternationalConference on Genetic Algorithms.San Mateo, T

CA: MorgankaufmannPublishers,Inc.,1989.

[144] Schneider,C.R.andH.C.Card, CMOS mean fieldlearning,”Electronics Letters,vol.27,no.19, E

September 121991,pp.1702—1703.

[145] Schwartz,M.,Telecommunication Networks: Protocols,Modeling and Analysis.Reading,MA: O

Addison-Wesley,1987.

[146] Sechen,C.,Placement andGlobalRoutingof IntegratedCircuits UsingtheSimulatedAnnealing H

Algorithm,Universityof Californiaat Berkeley,Ph.D.Dissertation,1986.

[147] Sengoku, M., K. Nakano and Y. Yamaguchi,“Channel assignment in a cellular mobile

#第124页-

communicationsystemandanapplicationofneuralnetworks,”Electronics&Communicationsin

Japan,Part 1,vol.75,no.4,April1992,pp.24—36.

[148] Skea, D.,I.Barrodale,R.Kuwahara and R.Poecker,“A control point matching algorithm,” Y

PatternRecognition,vol.26,no.2,February1993,pp.269—276.

[149] Snyder,W.,A.Logenthiran and P.Santago,“Segmentation of magneticresonanceimages using W

meanfieldannealing,”ImageandVisionComputing,vol.10,no.6,July1992,pp.361—368.

[150] Spears,W.M.andK.A.DeJong,“Onthe virtues of parameterizeduniform crossover,”Proc.of E

theFourth InternationalConferenceon GeneticAlgorithms,pp.230—236,1991.SanMateo,CA:

MorgranKaufmanPublishers.

[151] SpecialIssueon ComputationalandArtificialIntelligenceinHigh SpeedNetworks,IEEEJournal E

onSelectedAreas in Communications,vol.15,no.2,February,1997.

[152] Sridhar, J. and C. Rajendran,“Scheduling in a cellular manufacturing system: a simulated d

annealing approach,”International Journal of Production Research, vol.31, no. 12,December

1993,pp.2927—2946.

[153] Syswerda,G.,“Uniform crossover,”Proc.of the Third International Conference on Genetic d

Algorithms,1989,pp.2—9.

[154] Staniforth, P. R.,“Store-andforward- satellite communications system on UOSAT-2,”The n

Journalof theInstitutionof ElectronicandRadioEngineers,vol.57,January1987,p.43.

[155] Szu,H.H.andR.Hartley, Fast simulatedannealing,”Physics Letters A,vol.122,June1987,pp. E

157—162.

[156] Szu,H.H.and R.Hartley,“Nonconvex optimization by fast simulated annealing,”Proc.of the S

IEEE,vol.75,November 1987,pp.1538—1540.

[157] Szykman, S. and J. Cagan,“A simulated annealing-based approach to three-dimensional

component packing,”Journalof MechanicalDesign,vol.117,no.2,June1995pp.308—314.

[158] Thouless,D.J.,P.W.AndersonandR.G.Palmer, Solutionof‘solvablemodelofaspinglass’,” H

PhilosophicalMagazine,vol.35,no.3,1977,pp.593—601.

[159] Tan,H.L.,S.B.Gelfand and E.J.Delp,“A cost minimization approach toedge detection using S

simulated annealing,”IEEE Trans.on Pattern Analysis andMachineIntelligence,vol.14,no.1,

January1992,pp.3—18.

[160] Tanaka,Y. and S.Hosaka,“Fuzzy control of telecommunications networks using automatic k

learning technique,”Electronics & communications in Japan—Partl,vol. 76,no.12,December

1993,pp.41—51.

[161] Umeyama,S.,“Parameterized point pattern matchingandits application to recognition of object L

families,”IEEE Trans.on Pattern Analysis and Machine Intelligence, vol. 15,no.2,February

1993,pp.136—144.

[162] Van den Bout,D.E.andT.K.Miller,III,“Graph partitioning using annealed networks,”IEEE Z

Trans.onNeuralNetworks,vol.1,no.2,1990,pp.192—203.

[163] Van Laarhoven,P.J.M.and E.H.L.Aarts,Simulated Annealing: Theory and Applications. X

Dordrecht,Holland: D.Reidel PublishingCompany,1987.

[164] Vecchi, M. P. and S. Kirkpatrick,“Global wiring by simulated annealing,”IEEE Trans. on h

Computer-AidedDesign,vol.2,1983,pp.215—222.

[165] Wang,G.andN.Ansari, A neuralnetworkapproach tobroadcast schedulinginmulti-hopradio I

#第125页-

networks,”Proc.1994 IEEE Conference on Neural Networks,Orlando,FL.,June 28-July 2,

1994,pp.4699—4703.

[166] Wang,G.and N.Ansari,“Maximizing data throughput in an integrated TDMA communication ^

systemusingmeanfieldannealing,”Proc.1994IEEEConferenceonGlobalTelecommunications,

SanFrancisco,CA.,November 28—December 2,1994,pp.329—333.

[167] Wang,G.andN.Ansari, Optimalbroadcastschedulinginpacketradionetworks usingmeanfield F

annealing,”IEEE Journal on Selected Areas in Communications,vol.15,no.2,February,1997,

pp.250—266.

[168] Wayman,J.L.,“Optimization of signal distribution networks usingsimulatedannealing,”IEEE H

Trans.onCommunications,vol.40,no.3,March 1992,pp.465—471.

[169] Witte, E. E., R. D. Chamberlain and M. A. Franklin,“Parallel simulated annealing using x

speculative computation,”IEEE Trans. on Parallel and Distributed Systems, vol. 2, no. 4,

October 1991,pp.483—494.

[170] Wolberg,G.and T. Pavlidis,“Restoration of binary images using stochastic relaxation with b

annealing,”PatternRecognitionLetters,vol.3,1985,pp.375—388.

[171] Wong, K. P. and Y. W. Wong,“Genetic and genetic/simulated-annealing approaches to  ̄

economic,”IEE Proc.—C,Generation,Transmission,andDistribution,vol.141,no.5,September

1994,pp.507—513.

[172] Woodruff,D.L.,“Simulatedannealingandtabusearch: Lessons from a linesearch,”Computers I

andOperationsResearch,vol.21,no.8,1994,pp.823—840.

[173] Wu,G.and J.W.Mark,“Capacity allocation for integrated voice/data transmission at a packet L

switchedTDM,”IEEETrans.onCommunications,vol.40,June1992,pp.1059—1069.

[174] Yip,P.P.CandP.-H.Pao,“Combinatorialoptimizationwithuseofguidedevolutionarysimulated F

annealing,”IEEETrans.on NeuralNetworks,vol.6,no.2,March1995,pp.290—295.

[ 175] Yuhas, B. and N. Ansari, (eds.), Neural Networks in Telecommunications. Norwell, MA: y

Kluwer,1994.

[176] Yuille, A. L., D. Geiger and H. H. Bulthoff,“Stergo integration, mean field theory and s

psychophysics,”Network: Computation in Neural Systems,vol.2,no.4,November 1991,pp.

423—442.

[177] Zerubia,J.andR.Chellappa, MeanfieldannealingusingcompoundGauss-Markovrandomfields E

for edge detection and image estimation,”IEEE Trans.on Neural Networks,vol.4,no.4,July

1993,pp.703—709.

[178] Zhang,Z.Z.,N.Ansari,E.Hou and P.Yi,“Multiprocessor scheduling by mean field theory,” a

Proc.of theIJCNN-92,Vol.IV,June1992.pp.582—587.

[179] Zhao, M., N. Ansari and E. S. H. Hou,“Mobile manipulator path planning by a genetic t

algorithm,”Journalof RoboticSystems,vol.11,no.3,pp.143—153,1994.

[180] Zhou,D.N.,V.Cherkassky,T.R.Baldwin,and D.E.Olson,“A neuralnetwork approachtojob- I

shopscheduling,”IEEETrans.on NeuralNetworks,vol.2,no,1,January1991,pp.175—179.

#第126页-

名词术语中英文对照表( 以汉语拼音排序)

two-dimensional ( 2-D ) 9

A 二维点模式 point pattern

鞍点 saddlepoint

鞍点逼近 saddle-point approximation F

鞍点展开 saddle-point expansion 放大器 amplifier

非对称均场网络 asymmetric mean-field

B network

复杂度 complexity

玻耳兹曼常数 Boltzmannconstant

玻耳兹曼分布 Boltzmanndistribution 复杂度函数 complexityfunction

本征值 反馈电路 feedback circuit

eigenvalue 繁殖

本征向量 reproduction

eigenvector 分次神经元

本征值分析 eigenvalueanalysis gradedneuron

本征空间 返回神经网络 recurrent neuralnetwork

eigenspace 分时多路存取 time-division multiple

玻尔兹曼机 Boltzmannmachine

access(TDMA)

白噪声 whitenoise

D G

概率密度函数 probability density

代数重数 algebraicmultiplicity

多项式时间 function

polynomialtime

动态系统 dynamicsystem 归一化吞吐量 normalizedthroughput

高斯机 Gaussianmachine

动力学 dynamics

更新 updating

定长边界 fixedlength boundary

等位基因 alleles H

代 generation

单调增函数 monotonically increasing 回溯 backtracking

function J

多处理器调度问题 multiprocessor scheduling

problem 接受概率

点模式匹配 point patternmatching acceptanceprobability

调度 接受比 acceptanceratio

schedule 激活 activation

电信业务 telecommunications services

激活能 activationpotentials

多项式时间约化 polynomialtimereduction 接受规则

acceptancerule

E 均场退火 meanfieldannealing

渐近时间/空间复 asymptotic time/space

二值硬限器 binaryhardlimiters 杂度 complexity

二值符号串 binarystring 计算复杂度 computationalcomplexity

#第127页-

计算智能 computationalintelligence N

计算机辅助设计 computer-aideddesign

计算机视觉 computer vision

N-皇后问题 N-Queenproblem晶体 crystalline NP完全理论 theory of NP-距离矩阵 distancematrix

距离参数 completeness

distanceparameter

几何重数 geometricmultiplicity P

结构单元 buildingblocks

泊松过程 Poissonprocess

基因 gene

交叉 crossover Q

局部搜索 localsearch

局部最小 localminima 群体 population

均场逼近 meanfieldapproximation 全局最小 globalminima

均场方程 meanfieldequation 启发函数 heuristicfunction均场网络 meanfieldnet 启发搜索 heuristicsearch

均场变量 meanfieldvariable 群体空间 population space

均场向量 meanfieldvector R

决策问题 decisionproblems

计算复杂性理论 theory of computational 扰动规则

pertubationrule

complexity 染色体 chromosome

均匀分布 uniformdistribution

锐化 sharpening

软限幅器 soft-limiter

K 任务图

taskgraph

空间复杂度 spacecomplexity 热力学 thermodynamics

可按内容检索的 content addressable

记忆 memory(CAM) S

柯西机 Cauchymachine 算法

可满足性问题 satisfiabilityproblem algorithm

双极 bipolar

L 数据吞吐量 datathroughput

数据结构 datastructure

连接矩阵 connectionmatrix 适度值 fitness value

临界温度 criticaltemperature 适度函数 fitness function

累积高斯分布函数 cumulative Gaussian 形函数

S Sigmoidfunction

distribution 随机噪声 randomnoise

拉格朗日参数 Lagrangeparameter 随机数 randomnumber

旅行商问题 traveling salesman 随机数发生器

randomnumber generator

problem(TSP) 随机点过程 randompoint process

M 随机过程 randomprocess

随机搜索 randomsearch

随机变量 randomvariable

模拟退火 simulatedannealing

马尔可夫链 收敛速率 rateof convergence

Markovchain 随机激活函数

模式识别 stochastic activation

patternrecognition

function

#第128页-

随机方程 stochasticequations X

随机机 stochasticmachine

随机神经元 stochasticneurons

选择规则 selectionrules

随机松弛法 stochasticrelaxation 形状特征

扫描 shapefeatures

sweep 形状识别 shaperecognition随机更新 stochasticupdating

相似变换 similaritytransformation尝试法 trialanderror

T Y

异步传递方式 asynchronous transfer退火 annealing

退火过程 mode

annealingprocess 有色噪声

退火流程 annealingschedule colorednoise

一致性函数 consensus function突变 mutation

统计力学 遗传算法 geneticalgorithms

statisticalmachanics 异联想 -

统计物理学 statisticalphysics heteroassociative

硬限器 hardlimiter

停止准则 stoppingcriterion 异步更新 asynchronous updating停止参数 stoppingparameter

同步更新 synchronous updating Z

特征方程 characteristicequation

自联想 auto-associative

特征多项式 characteristicpolynomial

指数函数 exponentialfunctions

W 指数时间 exponentialtime

帧格式 frameformat

卫星广播调度 satellite broadcast

帧模式 framepattern

scheduling(SBS)

稳定性 直方图 histograms

stability 作业调度问题

job shop scheduling稳定构形 stableconfiguration problem

稳定点 stablepoint

稳定状态 最小生成树 minimumspanningtree

stablestate 最优化问题 optimizationproblem稳态 steadystate 最优调度

optimalschedule

终止准则 terminationcriteria

#第129页-