三维曲面上路径规划问题的研究
摘要
在给定曲面上的两点间求沿曲面的最短路径，是理论与实际领域都十分关注的问题。由于自由曲面自身的复杂性，需要找到一种既准确又可靠，并能广泛适用于自由曲面的求取方法。三维曲面最短路径的求解方法可以有效地解决形式各异的曲面路径优化问题。如果将其用于战场、公路、铁路建设，电力、通信线路，输水、输油管道的假设等实际问题中，可以起到立竿见影的效果，将节省大笔开支。
三维图形对象表示方法大致可以分为两类，即边界(Boundary)表示和实体表示(Solid)。边界表示包括多边形网格、隐式曲面、参数曲面模型，其中隐式曲面、参数曲面一般通过转换为多边形网格模型进行绘制。实体表示包括结构实体模型(CSG)和分解模型，其中结构实体模型最终需要转换为实体的边界表示进行绘制，而分解模型的最基本元素是体素。所以从绘制的角度看，也可以把三维图形对象的表示分为曲面模型(本文的研究重点)和体素模型(简称体模型)，曲面模型中可以用栅格作为典型。
栅格数据结构和矢量数据结构都是表示空间数据的有效方法，但是都有一定的优点和局限性。矢量数据能输出精美的地图，但结构复杂，用于空间分析存在不少的困难，尤其是在多边形的叠置、空间均值处理上。相比之下，栅格数据数据结构简单，叠加操作易于实现，更有效，如多边形周长、面积总和、平均值的计算等，在栅格结构中都简化为简单的计数操作，栅格坐标规则，删除和提取数据都可以按位置确定窗口来实现。
规则格网是比较普遍采用的表示方法。用Grid表示的DEM是一种XY平面等间距排列地面点XYZ三维坐标的数据形式。它的数据格式比较的简单，便于存储，建模方法也比较直接，所描述的高程细节信息也比较的丰富；采用不规则三角网表示的DEM称为三角网DEM或Tin(Triangulated irregular network)，它直接利用原始的离散采样点表示地形表面，因此Tin不仅有地面点XYZ的三维坐标，保持了原始采样数据的精度，还包含了三角网构网的拓扑信息，比较适合描述复杂的地形数据。但是三角形面元，以及三角形点、边之间的拓扑关系比较复杂，要对其进行处理也比较复杂。基于TIN模型的DEM简化计算在预处理和可视化的实时计算量比较大，难以处理跨区域DEM实时漫游，而且时显示时很难具有自适应能力；相比之下，规则格网结构简单，算法容易，可视化实时计算量小。
路径规划问题是人工智能研究的一个经典问题，它实际是一类求最优解的问题。其实现过程就是从问题的初始状态出发，不断地选择合适的操作来不断的改变问题的状态，直到满足目标状态为止，实现过程中所运用的操作序列就构成了问题的解。搜索的过程可以分为三个部分：一是选择合适的操作，二是记住已施行的操作序列，三是描述操作所产生的状态。求最优解或近似最优解方法可以分为枚举法、Dijkstra算法、传统的启发式算法和新兴的启发式算法——遗传算法等几种类型。利用启发式方法对三维曲面路径问题进行求解有比较重要的意义，能够求出比直接连线法更好的路径。且在计算过程中启发式算法的微调能力是
Finding an algorithm for solving the minimal way on surface is concerned by theoretical and practical areas.The algorithm can be used for practical applications such as battlefield, the constructions of railway and highway, and so on.
There are two ways to represent the 3D graphic objects: Boundary and Solid. Boundary includes polygon grid and parametric surface. Solid includes CSG and decompose model.So from the view of draw, 3D graphic objects can be represented to surface model and tissue model ,and grid can be the example for surface model.
As two available approaches to represent 3D data, grid data structure and vector data structure both have advantages and limitations. Vector data structure can export fancy maps, but the constructor is too complex.In contract, grid data structure has a compact constructor and efficiency for use.
Order grid is an offen adopted represent for 3D data. It use grid to represent DEM. The data format is simple, and easy to store. Triangulated irregular network is another way to represent DEM.It is very suitable for complex landform, but it has a complex topological relation to deal with.In contrast, order grid can be use easily.
Path planning is a classical problem of AI. It starts from an initial state, and constantly chooses appropriate operate to change the state until reaches the goal state.There are many type of algorithm for solving the minimal way such as enumeration method, Dijkstra algorithm,traditional heuristic algorithm and genetic algorithm. Heuristic algorithm has the great significance for solving the minimal way on surface.
After analysed the way to represent the 3D graphic objects and path planning finding, a new algorithm based on genetic algorithm and surface thinning for path planning on 3D surface is brought on.
For the expression method of the environmental model, order grids are used to represent the 3D graphic objects in this paper. This can make solving simplify.
An algorithm called Guotao Algorithm (GT) owned to Evolutionary Algorithm and surface thinning are used to find the minimal way on surface in this paper.
GT is from TSP and plan on the minimal way on surface the differences of issues route in issueses, effective range in chromosomes(from the starting point to terminal point in the genes) and the range of choosings of genes (select gene C from the starting point to terminal point in the genes, select gene C from the Gene Database of C), wait for place revise to the algorithm, Introduce gene pool come and optimize some algorithms.Most way for surface thinning are fractionizing the whole surface. But this paper only fractionize the areas near the minimal way. The scale of problem is reduced in this way.
Related algorithms are verified by the results of programs, attaining to the requirement.
三维图形对象表示方法大致可以分为两类，即边界(Boundary)表示和实体表示(Solid)。边界表示包括多边形网格、隐式曲面、参数曲面模型，其中隐式曲面、参数曲面一般通过转换为多边形网格模型进行绘制。实体表示包括结构实体模型(CSG)和分解模型，其中结构实体模型最终需要转换为实体的边界表示进行绘制，而分解模型的最基本元素是体素。所以从绘制的角度看，也可以把三维图形对象的表示分为曲面模型(本文的研究重点)和体素模型(简称体模型)，曲面模型中可以用栅格作为典型。
栅格数据结构和矢量数据结构都是表示空间数据的有效方法，但是都有一定的优点和局限性。矢量数据能输出精美的地图，但结构复杂，用于空间分析存在不少的困难，尤其是在多边形的叠置、空间均值处理上。相比之下，栅格数据数据结构简单，叠加操作易于实现，更有效，如多边形周长、面积总和、平均值的计算等，在栅格结构中都简化为简单的计数操作，栅格坐标规则，删除和提取数据都可以按位置确定窗口来实现。
规则格网是比较普遍采用的表示方法。用Grid表示的DEM是一种XY平面等间距排列地面点XYZ三维坐标的数据形式。它的数据格式比较的简单，便于存储，建模方法也比较直接，所描述的高程细节信息也比较的丰富；采用不规则三角网表示的DEM称为三角网DEM或Tin(Triangulated irregular network)，它直接利用原始的离散采样点表示地形表面，因此Tin不仅有地面点XYZ的三维坐标，保持了原始采样数据的精度，还包含了三角网构网的拓扑信息，比较适合描述复杂的地形数据。但是三角形面元，以及三角形点、边之间的拓扑关系比较复杂，要对其进行处理也比较复杂。基于TIN模型的DEM简化计算在预处理和可视化的实时计算量比较大，难以处理跨区域DEM实时漫游，而且时显示时很难具有自适应能力；相比之下，规则格网结构简单，算法容易，可视化实时计算量小。
路径规划问题是人工智能研究的一个经典问题，它实际是一类求最优解的问题。其实现过程就是从问题的初始状态出发，不断地选择合适的操作来不断的改变问题的状态，直到满足目标状态为止，实现过程中所运用的操作序列就构成了问题的解。搜索的过程可以分为三个部分：一是选择合适的操作，二是记住已施行的操作序列，三是描述操作所产生的状态。求最优解或近似最优解方法可以分为枚举法、Dijkstra算法、传统的启发式算法和新兴的启发式算法——遗传算法等几种类型。利用启发式方法对三维曲面路径问题进行求解有比较重要的意义，能够求出比直接连线法更好的路径。且在计算过程中启发式算法的微调能力是
Finding an algorithm for solving the minimal way on surface is concerned by theoretical and practical areas.The algorithm can be used for practical applications such as battlefield, the constructions of railway and highway, and so on.
There are two ways to represent the 3D graphic objects: Boundary and Solid. Boundary includes polygon grid and parametric surface. Solid includes CSG and decompose model.So from the view of draw, 3D graphic objects can be represented to surface model and tissue model ,and grid can be the example for surface model.
As two available approaches to represent 3D data, grid data structure and vector data structure both have advantages and limitations. Vector data structure can export fancy maps, but the constructor is too complex.In contract, grid data structure has a compact constructor and efficiency for use.
Order grid is an offen adopted represent for 3D data. It use grid to represent DEM. The data format is simple, and easy to store. Triangulated irregular network is another way to represent DEM.It is very suitable for complex landform, but it has a complex topological relation to deal with.In contrast, order grid can be use easily.
Path planning is a classical problem of AI. It starts from an initial state, and constantly chooses appropriate operate to change the state until reaches the goal state.There are many type of algorithm for solving the minimal way such as enumeration method, Dijkstra algorithm,traditional heuristic algorithm and genetic algorithm. Heuristic algorithm has the great significance for solving the minimal way on surface.
After analysed the way to represent the 3D graphic objects and path planning finding, a new algorithm based on genetic algorithm and surface thinning for path planning on 3D surface is brought on.
For the expression method of the environmental model, order grids are used to represent the 3D graphic objects in this paper. This can make solving simplify.
An algorithm called Guotao Algorithm (GT) owned to Evolutionary Algorithm and surface thinning are used to find the minimal way on surface in this paper.
GT is from TSP and plan on the minimal way on surface the differences of issues route in issueses, effective range in chromosomes(from the starting point to terminal point in the genes) and the range of choosings of genes (select gene C from the starting point to terminal point in the genes, select gene C from the Gene Database of C), wait for place revise to the algorithm, Introduce gene pool come and optimize some algorithms.Most way for surface thinning are fractionizing the whole surface. But this paper only fractionize the areas near the minimal way. The scale of problem is reduced in this way.
Related algorithms are verified by the results of programs, attaining to the requirement.
引文
[1] DOD. Modeling and Simulation Master Plan. Department of Defense, 1995.
[2] 涂晓媛．人工鱼——计算机动画的人工生命方法．北京：清华大学出版社，2005．12-22
[3] 刘刚，金小刚，冯结青，彭群生．蒙太奇网格融合．软件学报，vol．14，no．8，pp．1425-1432，2005．
[4] 毛伟，潘红，吴飞，庄越挺．基于深度加权法向映射的三维模型检索，vol．17，no．2，pp．247-252，2005．
[5] Huang J., Yagel R. Filippov V. and Kurzion Y. An Accurate Method for Voxelizing Polygon Meshes. Proc. ofIEEE Symposium on Volume Visualization, pp. 119-126, 1998.
[6] Cohen-Or D., Kaufman A. Fundamentals of Surface Voxelization. Graphics Models and Image Processing, vol. 57, no. 6, pp. 453-461, 1995.
[7] Alexa M. Merging Polyhedral Shapes with Scattered Features, The Visual Computer, vol. 16, no. 1, pp. 26-37, 2000.
[8] Cohen-Or D, Levin D. and Solomovic A. Three-Dimensional Distance Field Metamorphosis. ACM Transactions on Graphics, vol. 17, no. 2, pp.116-141, 1997.
[9] Kaufman A. and Shimony E. 3D Scan-conversion Algorithms for Voxel-based Graphics. Proc. of ACM Workshop on Interactive 3D Graphics, pp.45-76, 1986.
[10] Kaufman A. Efficient Algorithms for 3D Scanconversion of Parametric Curves, Surfaces, and Volumes. SIGGRAPH, pp.171-179, 1987.
[11] Kaufman A. Efficient Algorithms for Scan-converting 3D Polygons, Computers and Graphies. vol. 12, no. 2, pp. 213-219, 1988.
[12] Bresenham E. A Linear Algorithm for Incremental Digital Display of Circular Arcs Communication of ACM, vol. 20, no. 2, pp.100-106, 1977.
[13] Foley J. D. and Dam A. Fundamental of Interactive Computer Graphics, Addison-Wesley, Reading, MA, 1982.
[14] Amanatides J. and Woo A. A Fast Voxel Traversal Algorithm for Ray Tracing. Eurographics, pp. 3-9, 1987
[15] Cohen-Or D, and Kaufman A. 3D Line Voxelization and Connectivity Control. IEEE Computer Graphics and Applications. vol. 17, no. 6, pp.80-87, 1997.
[16] Amanatides J. and Woo A. A Fast Voxel Traversal Algorithm for Ray Tracing. Eurographics, pp. 3-9, 1987
[17] Andres E. Nehlig P. and Francon J. Tunnel-Free Supercover 3D Polygons and Polyhedra. EG Computer Graphics Forum, vol. 16, no. 3, pp.3-14, 1997.
[18] Huang J., Yagel R. Filippov V. and Kurzion Y. An Accurate Method for Voxelizing Polygon Meshes. Proc. ofIEEE Symposium on Volume Visualization, pp.119-126, 1998.
[19] Fang S. F and Chen H. Hardware Accelerated Voxelization. Computer&Graphics, vol. 24, no. 3,433-442, 2000.
[20] Liao D. D. and Fang S. F. Fast Volumetric CSG Modeling using Standard Graphics System. Proc. of Ts ACM Symposium on Solid Modeling and Applications, pp. 204-211, 2002
[21] Haumont D. and Warzee N Tools, vol. 7, no. 3, pp27-41Complete Polygonal Seen Voxelization. Journal of Graphics 2002
[22] Fang S. F and Chen H. Hardware Accelerated Voxelization. Computer&Graphics, vol. 24, no. 3,.433-442, 2000.
[23] Fakir S. N. and Greg T. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Transactions on Visualization and Computer Graphics. vol. 9, no. 2, pp. 191-205,2003.
[24] Rueda A.J. et. al. Voxelization Solids using Simplicial Coverings. Journal of WSCG, vol. 12 no. 2, pp. 227-234, 2004.
[25] Feito, F., Torres, J.C., Boundary Representation of Polyhedral Heterogeneous in the Context of a Graphic Object Algebra. The Visual Computer; vol.13, no.2, pp. 64-77,1997.
[26] Feito, F., Torres, J.C., Inclusion test in General Polyhedra. Computer&Graphics, vol. 21, no. 1, pp. 23-30, 1997.
[27] Karabassi A., Papaioannou G. and Theoharis T. A Fast Depth-buffer-based Voxelization Algorithm. Journal of Graphics Tools, vol. 14, no, 4, pp.5-10, 1999.
[28] Passalis G., Kakadiaris A. and Theohafis T. Efficient Hardware Voxelization. Proc. of IEEE Computer Graphics International, pp. 374-377, 20D4.
[29] M. T., Kato T., and Otsu N. A Similarity Retrieval of 3D Polygonal Models using Rotation Invariant Shape Descriptors. IEEE International Conference on System, Man, and Cybernetics, PP2946-2952,2000.
[30] Ankerst M., Kasteumuller G., Kfiegel H. P. and Seidl T. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. 6th International Symposium on Advances in Spatial Databases, vol. 1651, pp. 207-228, 1999.
[31] 孙家广，陈玉健，辜凯宁．计算机辅助几何造型技术．北京：清华大学出版社，1990．
[32] Lane J M, Riesenfeld R F, A theoretical development for the computer generation and display of piecewise polynomial surface. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, PAMI-2(1).
[33] 黄樟灿，陈思多，康立山等．基于模拟退火算法的曲面最短路径求解．武汉大学学报(自然科学版)，2000．6
[34] R. Chatila. Path Planning and Environment Learning in a Mobile Robot System. In: Proc of the European Conf on AL. Geneva, Switzerland. 1982. 155～166
[35] Chen Gang and Shen Lincheng. Genetic Path Planning Algorithm for Complex Environment Path Planning. Robot. 2001, 23(1): 40～50
[36] 陈阳，吴裕树，史万明．机器人路径规划的凸点法．北京理工大学学报，1995，15(5)：17～20
[37] M. Dorigo, V. Maniezzo. A. Colomi. Ant system: optimization by a colony by cooperating agent. IEEE Transactions on Systems , Man andCybernetics (Part-B), 1996, 26(1): 29～41
[38] 冉瑞江等．曲线曲面的若干几何处理基础算法研究．北京航空航天大学学报，1996．8．
[39] 苏智剑等．遗传算法在求解空间曲线与曲面间最短距离中的应用．机械设计与制造，2003．12
[40] 朱心雄．自由曲线曲面造型技术[M]．北京．科学出版社，2000
[41] Cohen-Or D, and Kaufrnan A. 3D Line Voxelization and Connectivity Control. IEEE Computer Graphics and Applications. vol. 17, no. 6, pp.80-87, 1997.
[42] Cohen-Or D, Levin D. and Solomovic A. Three-Dimensional Distance Field Metamorphosis. ACM Transactions on Graphics, vol. 17, no. 2, pp.116-141, 1997.
[43] Cong G. Esscr M. Parvin B. and Bebis G. Shape Metamorphosis using p-Laplacian Equation. International Conference on Pattern Recognition, pp. 23-26, 2004.
[44] DeCarlo D. and Gallier J. Topological Evolution of Surfaces. Graphics Interface, pp. 194-203,1996.
[45] Dong F., Clapworthy G. 1. and Krokos M. Volume Rendering of Fine Details within Medical Data. Proc. of the Conference on Visualization, pp. 387-394, 2001.
[46] Danielsson P. E. Euclidean Distance Mapping. Computer Graphics and Image Processing. vol. 14, pp. 227-248, 1980.
[47] Ray, T., TRai, K. and Scow, K. C. (2001). An evolutioanry algorithm for multiobjecvtive optimization. Engineering Optimization 33(3), 399-424.
[48] Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T. (2000). A fast and elitist multiobjective genetic algorithm: NSGAⅡ. Technical Report 200001, Indian Institute of Technology, Kanpur:Danpur Genetic Algorithms Laboratory (KanGAL).
[49] Rudolph, G. (2001). A Partial Order Approach to Noisy Fitness Functions. Proceedings of the 2001 Congress on Evolutionary Com-putation (CEC 2001), pp. 318-325. Seoul Korea.
[50] Greene J., (July 1997) Simulated Evolution and Adaptive Search in Engineering Design-Experiences at the University of Cape Town, in 2nd Online Workshop on Soft Computing.
[51] LANGTON C., "Artificial Life", in Boden M., The Philosophy of Artificial Life, Oxford Readings in Philosophy, Oxford University Press, 1996, pp.39-94.
[52] ORTEGA C. and TYRRELL A., "Fault-tolerant Systems: The way Biology does it!", Procs. Euromicro 97, short contributions, IEEE Computer Society Press, to be published.
[53] Tempesti G., "A Robust Multiplexer-based FPGA Inspired by Biological Systems", Special Issue of JSA on Dependable Parallel Computer Systems, Feb. 1997, pp.719-733
[54] J. Von Neumann, Theory of self-reproducing automata(ed A. W. Burks), University of Illionis, Urbana, 1966
[55] Mitchell M., An Introduction to Genetic Algorithms.Cambridge, MIT Press,1996
[56] J.H. Holland, Adaptation in Natural and Artificial System, The University of Michigan Press, 1975
[57] J D Schaffer. Some Experiments in Machine Learning Using Vector Evaluated GAs. Ph. D. Thesis, Nashville, TN: Vanderbilt University, 1984.
[58] D Goldberg Genetic Algorithms for Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
[59] Fogel D B., Evolving programing for training neural networks,International Joint Conf.. on Neural Networks'90, Washington, D.C., 1990,601-605
[60] Bethke A D. , Genetic algorithms as function optimizers, PH.D.diss., University of Michigan, 1981
[61] IEEE. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press. 2 volumes. 1994.
[62] IEEE. Proceedings of the Second IEEE Conference on Evolutionary Computation. IEEE Press. 2 volumes. 1995.
[62] IEEE. Proceedings of the Third IEEE Conference on Evolutionary Computation. IEEE Press. 1996.
[63] IEEE. Proceedings of the Fourth IEEE Conference on Evolutionary Computation. IEEE Press. 1997
[64] IEEE. Proceedings of the 1998 IEEE Conference on Evolutionary Computation, Anchorage, Alaska, May 4 - 9, 1998. Piscataway, NJ: IEEE. 1 volume. NOTE: This event was part of the 1998 IEEE World Congress on Computational Intelligence. 1998.
[65] IEEE Neural Networks Council (Editor). Proceedings of the 2001 Congress on Evolutionary Computation: Cec2001, May 27-30, COEX Center, Seoul, Korea, IEEE-Press, 2001
[66] IEEE Neural Networks Council. Proceedings of the 2002 Congress on Evolutionary Computation: Hilton, Hawaiian Village Hotel, Honolulu, Hawaii, May 12-17, IEEE-Press, 2002
[67] Ruhul Sarker, Robert Reynolds, Hussein Abbass, Kay Chen Tan, Bob McKay, Daryl Essam, Tom Gedeon Proceedings of the 2003 Congress on Evolutionary Computation: Canberra, Australia, December 8-12, IEEE-Press, 2003
[68] L. Spector, E. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon & E. Burke (Eds), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). San Francisco, CA: Morgan Kaufmann Publishers,
[69] W. B. Langdon, et al. (editors), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2002, San Francisco, CA: Morgan Kaufmann Publishers.
[70] Genetic and Evolutionary Computation—GECCO 2003: Genetic and Evolutionary Computation Conference, Chicago, IL, USA, July 2003, vol. LNCS 2724, Lecture Notes in Computer Science, E. Cantu-Paz, J. A. Foster, K. Deb, L. D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. A. Dowsland, and N. J. J. Miller, Eds. Berlin: Springer-Verlag, 2003,
[71] Zitzler, Eckart, Deb, Kalyanmoy, Thiele, Lothar, Coello Coello, Carlos A., and Corne, David (editors). 2001. Evolutionary Multi-Criterion Optimization, First International Conference, EMO 2001, Zurich, Switzerland, March 2001, Proceedings. Lecture Notes in Computer Science. Volume 1993. Berlin, Germany: Springer-Verlag.
[72] Fonseca, Carlos M., Fleming, Peter J., Zitzler, Eckart, Deb, Kalyanmoy, and Thiele, Lothar (editors). 2003. Evolutionary Multi-Criterion Optimization: Second International Conference, EMO 2003, Faro, Portugal, April 2003 Proceedings. Lecture Notes in Computer Science No. 2632. Berlin: Springer.
[73] Stoica, Adrian, Keymeulen, Didier, and Lohn, Jason (editors). 1999. Proceedings of the First NASA / DOD Workshop on Evolvable Hardware, Pasadena, California, July 19-21, 1999. Los Alamitos, CA. IEEE Computer Society.
[74] Lohn, Jason, Stoica, Adrian, Keymeulen, Didier, and Colombano, Silvano (editors). 2000. Proceedings of the Second NASA / DoD Workshop on Evolvable Hardware, July 13-15 2000, Palo Alto, California. Los Alamitos, CA: IEEE Computer Society Press.
[75] Keymeulen, Didier, Stoica, Adrian, Lohn, Jason, and Zebulum, Ricardo Salem (editors). 2001. Proceedings of the Third NASA/DOD Workshop on Evolvable Hardware, Pasadena, California, July 12-14,2001. Los Alamitos, CA. IEEE Computer Society.
[76] Stoica, Adrian, Lohn, Jason, Katz, Rich, Keymeulen, Didier and Zebulum, Ricardo Salem (editors). 2002. Proceedings of 2002 NASA/DoD Conference on Evolvable Hardware. Los Alamitos, CA: IEEE Computer Society.
[77] Lohn, Jason, Zebulum, Ricardo, Steincamp, James, Keymeulen, Didier, Stoica, Adrian, and Ferguson, Michael I. (editors). 2003. Proceedings of 2003 NASA/DoD Conference on Evolvable Hardware. Los Alamitos, CA: IEEE Computer Society
[78] Cohon, J. L. Multiobjective Programming and Planning. NewYork: Academic Press. David E Goldberg. 1978.
[79] Steuer, R. E. Multiple Criteria Optimization: Theory, Computation, and Applica- tion. New York: Wiley. 1986.
[80] Koski, J. (1984). Multicriterion optimization in structural design. In E. Atrek, R. H. Gallagher, K. M. Ragsdell, and O. C. Zienkiewicz (Eds.), New Directions in Optimum Structural Design, pp. 483C503. Wiley.
[81] Schaffer, J. D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. Ph. D. thesis, Vanderbilt University. Unpublished. 1984.
[82] Schaffer, J. D. Multiple objective optimization with vector evaluated genetic algorithms. In J. J. Grefenstette (Ed.),Proceedings of an International Conference on Ge- netic Algorithms and Their Applications, Pitts-burgh, PA, 1985. pp. 93C100. sponsored by Texas Instruments and U.S. Navy Center for Applied Research in Artificial Intelli- gence (NCARAI).
[83] Hajela, P. and C. Y. Lin. Genetic search strategies in multicriterion optimal design. Structural Optimization 1992, 4, 99C107.
[84] Fonseca, C. M. and P. J. Fleming. Genetic algorithms for multiobjective opti-mization: Formulation, discussion and generalization. In S. Forrest (Ed.), Proceed-ings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993, pp. 416C423. Morgan Kaufmann.
[85] Horn, J. and N. Nafpliotis. Multiobjective optimization using the niched pareto genetic algorithm. IlliGAL Report 93005, Illinois Genetic Algorithms Labo-ratory, University of Illinois, Urbana, Champaign. 1993.
[86] Horn, J., Nafpliotis, N. and Goldberg, D. E. A niched pareto genetic algo-rithm for multiobjective optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Computation, Vol-ume 1, Piscataway, NJ, 1994. pp. 82C87. IEEE.
[87] Srinivas, N. and Deb, K. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 1994,2(3), 221C248.
[88] Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T.. A fast elitist nondom-inated sorting genetic algorithm for multi-objective optimization: NSGAII. In M. S. et al. (Ed.), Parallel Problem Solving from Nature-PPSN VI, Berlin, 2000, pp. 849-858. Springer.
[89] Zitzler, E., Laumanns, M. and Thiele, L.. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103, 2001. ETH Zentrum, Gloriastrasse 35, CH-8092Zurich, Switxerland.
[90] Purshouse, R. C, Fleming, P. J.. The Multi-objective Genetic Algorithm Ap-plied to Benchmark Problems-an Analysis. Research Report No. 796. 2001 Department of Automatic Control and Systems Engineering University of Sheffield, Sheffield, S1 3JD, UK.
[91] Leung, Y. W. and Zhang, Q.. Evolutionary algorithms + experimenta design methods: A hybrid apprpach for hard optimization and search problems, Res. Grant Proposal, Hong Kong Baptist Univ. 1997.
[92] Wu, Q.. On the optimality of orthogonal experimental design. Acta Math Appl Sinica, 1978, vol. 1, no. 4, pp. 283-299.
[93] Leung, Y. W. and Wang, Y.. An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Trans. Evol. Comput. 2001, vol.5, No.1, pp. 40-53.
[94] Montgomery, D. C. Design and Analysis of Experiments. 3rd ed. 1991, New York: Wiley. [95] Hick, C. R. (1993). Fundamental Concepts in the Design of Experiments. 4th ed. TX: Saunders College Publishing.
[96] Zitzler, E.(1999). Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph. D. thesis, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland. TIK-Schriftenreihe Nr. 30, Diss ETH No. 13398, Shaker Verlag, Aachen, Germany
[97] M. Elad, A. Tal, and S. Ar. Content Based Retrieval of VRML Objects-An Iterative and Interactive Approach. 6th Eurographics Workshop in Multimedia, pp. 107-118,2001.
[98] Fakir S. N. and Greg T. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Transactions on Visualization and Computer Graphics, vol. 9, no. 2, pp. 191-205,2003.
[99] Fang S. F and Chen H. Hardware Accelerated Voxelization. Computer&Graphics, vol. 24, no. 3,433-442, 2000.
[100] 郭涛.演化计算与优化[博士学位论文].武汉:武汉大学.1999.P37-52.
[2] 涂晓媛．人工鱼——计算机动画的人工生命方法．北京：清华大学出版社，2005．12-22
[3] 刘刚，金小刚，冯结青，彭群生．蒙太奇网格融合．软件学报，vol．14，no．8，pp．1425-1432，2005．
[4] 毛伟，潘红，吴飞，庄越挺．基于深度加权法向映射的三维模型检索，vol．17，no．2，pp．247-252，2005．
[5] Huang J., Yagel R. Filippov V. and Kurzion Y. An Accurate Method for Voxelizing Polygon Meshes. Proc. ofIEEE Symposium on Volume Visualization, pp. 119-126, 1998.
[6] Cohen-Or D., Kaufman A. Fundamentals of Surface Voxelization. Graphics Models and Image Processing, vol. 57, no. 6, pp. 453-461, 1995.
[7] Alexa M. Merging Polyhedral Shapes with Scattered Features, The Visual Computer, vol. 16, no. 1, pp. 26-37, 2000.
[8] Cohen-Or D, Levin D. and Solomovic A. Three-Dimensional Distance Field Metamorphosis. ACM Transactions on Graphics, vol. 17, no. 2, pp.116-141, 1997.
[9] Kaufman A. and Shimony E. 3D Scan-conversion Algorithms for Voxel-based Graphics. Proc. of ACM Workshop on Interactive 3D Graphics, pp.45-76, 1986.
[10] Kaufman A. Efficient Algorithms for 3D Scanconversion of Parametric Curves, Surfaces, and Volumes. SIGGRAPH, pp.171-179, 1987.
[11] Kaufman A. Efficient Algorithms for Scan-converting 3D Polygons, Computers and Graphies. vol. 12, no. 2, pp. 213-219, 1988.
[12] Bresenham E. A Linear Algorithm for Incremental Digital Display of Circular Arcs Communication of ACM, vol. 20, no. 2, pp.100-106, 1977.
[13] Foley J. D. and Dam A. Fundamental of Interactive Computer Graphics, Addison-Wesley, Reading, MA, 1982.
[14] Amanatides J. and Woo A. A Fast Voxel Traversal Algorithm for Ray Tracing. Eurographics, pp. 3-9, 1987
[15] Cohen-Or D, and Kaufman A. 3D Line Voxelization and Connectivity Control. IEEE Computer Graphics and Applications. vol. 17, no. 6, pp.80-87, 1997.
[16] Amanatides J. and Woo A. A Fast Voxel Traversal Algorithm for Ray Tracing. Eurographics, pp. 3-9, 1987
[17] Andres E. Nehlig P. and Francon J. Tunnel-Free Supercover 3D Polygons and Polyhedra. EG Computer Graphics Forum, vol. 16, no. 3, pp.3-14, 1997.
[18] Huang J., Yagel R. Filippov V. and Kurzion Y. An Accurate Method for Voxelizing Polygon Meshes. Proc. ofIEEE Symposium on Volume Visualization, pp.119-126, 1998.
[19] Fang S. F and Chen H. Hardware Accelerated Voxelization. Computer&Graphics, vol. 24, no. 3,433-442, 2000.
[20] Liao D. D. and Fang S. F. Fast Volumetric CSG Modeling using Standard Graphics System. Proc. of Ts ACM Symposium on Solid Modeling and Applications, pp. 204-211, 2002
[21] Haumont D. and Warzee N Tools, vol. 7, no. 3, pp27-41Complete Polygonal Seen Voxelization. Journal of Graphics 2002
[22] Fang S. F and Chen H. Hardware Accelerated Voxelization. Computer&Graphics, vol. 24, no. 3,.433-442, 2000.
[23] Fakir S. N. and Greg T. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Transactions on Visualization and Computer Graphics. vol. 9, no. 2, pp. 191-205,2003.
[24] Rueda A.J. et. al. Voxelization Solids using Simplicial Coverings. Journal of WSCG, vol. 12 no. 2, pp. 227-234, 2004.
[25] Feito, F., Torres, J.C., Boundary Representation of Polyhedral Heterogeneous in the Context of a Graphic Object Algebra. The Visual Computer; vol.13, no.2, pp. 64-77,1997.
[26] Feito, F., Torres, J.C., Inclusion test in General Polyhedra. Computer&Graphics, vol. 21, no. 1, pp. 23-30, 1997.
[27] Karabassi A., Papaioannou G. and Theoharis T. A Fast Depth-buffer-based Voxelization Algorithm. Journal of Graphics Tools, vol. 14, no, 4, pp.5-10, 1999.
[28] Passalis G., Kakadiaris A. and Theohafis T. Efficient Hardware Voxelization. Proc. of IEEE Computer Graphics International, pp. 374-377, 20D4.
[29] M. T., Kato T., and Otsu N. A Similarity Retrieval of 3D Polygonal Models using Rotation Invariant Shape Descriptors. IEEE International Conference on System, Man, and Cybernetics, PP2946-2952,2000.
[30] Ankerst M., Kasteumuller G., Kfiegel H. P. and Seidl T. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. 6th International Symposium on Advances in Spatial Databases, vol. 1651, pp. 207-228, 1999.
[31] 孙家广，陈玉健，辜凯宁．计算机辅助几何造型技术．北京：清华大学出版社，1990．
[32] Lane J M, Riesenfeld R F, A theoretical development for the computer generation and display of piecewise polynomial surface. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, PAMI-2(1).
[33] 黄樟灿，陈思多，康立山等．基于模拟退火算法的曲面最短路径求解．武汉大学学报(自然科学版)，2000．6
[34] R. Chatila. Path Planning and Environment Learning in a Mobile Robot System. In: Proc of the European Conf on AL. Geneva, Switzerland. 1982. 155～166
[35] Chen Gang and Shen Lincheng. Genetic Path Planning Algorithm for Complex Environment Path Planning. Robot. 2001, 23(1): 40～50
[36] 陈阳，吴裕树，史万明．机器人路径规划的凸点法．北京理工大学学报，1995，15(5)：17～20
[37] M. Dorigo, V. Maniezzo. A. Colomi. Ant system: optimization by a colony by cooperating agent. IEEE Transactions on Systems , Man andCybernetics (Part-B), 1996, 26(1): 29～41
[38] 冉瑞江等．曲线曲面的若干几何处理基础算法研究．北京航空航天大学学报，1996．8．
[39] 苏智剑等．遗传算法在求解空间曲线与曲面间最短距离中的应用．机械设计与制造，2003．12
[40] 朱心雄．自由曲线曲面造型技术[M]．北京．科学出版社，2000
[41] Cohen-Or D, and Kaufrnan A. 3D Line Voxelization and Connectivity Control. IEEE Computer Graphics and Applications. vol. 17, no. 6, pp.80-87, 1997.
[42] Cohen-Or D, Levin D. and Solomovic A. Three-Dimensional Distance Field Metamorphosis. ACM Transactions on Graphics, vol. 17, no. 2, pp.116-141, 1997.
[43] Cong G. Esscr M. Parvin B. and Bebis G. Shape Metamorphosis using p-Laplacian Equation. International Conference on Pattern Recognition, pp. 23-26, 2004.
[44] DeCarlo D. and Gallier J. Topological Evolution of Surfaces. Graphics Interface, pp. 194-203,1996.
[45] Dong F., Clapworthy G. 1. and Krokos M. Volume Rendering of Fine Details within Medical Data. Proc. of the Conference on Visualization, pp. 387-394, 2001.
[46] Danielsson P. E. Euclidean Distance Mapping. Computer Graphics and Image Processing. vol. 14, pp. 227-248, 1980.
[47] Ray, T., TRai, K. and Scow, K. C. (2001). An evolutioanry algorithm for multiobjecvtive optimization. Engineering Optimization 33(3), 399-424.
[48] Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T. (2000). A fast and elitist multiobjective genetic algorithm: NSGAⅡ. Technical Report 200001, Indian Institute of Technology, Kanpur:Danpur Genetic Algorithms Laboratory (KanGAL).
[49] Rudolph, G. (2001). A Partial Order Approach to Noisy Fitness Functions. Proceedings of the 2001 Congress on Evolutionary Com-putation (CEC 2001), pp. 318-325. Seoul Korea.
[50] Greene J., (July 1997) Simulated Evolution and Adaptive Search in Engineering Design-Experiences at the University of Cape Town, in 2nd Online Workshop on Soft Computing.
[51] LANGTON C., "Artificial Life", in Boden M., The Philosophy of Artificial Life, Oxford Readings in Philosophy, Oxford University Press, 1996, pp.39-94.
[52] ORTEGA C. and TYRRELL A., "Fault-tolerant Systems: The way Biology does it!", Procs. Euromicro 97, short contributions, IEEE Computer Society Press, to be published.
[53] Tempesti G., "A Robust Multiplexer-based FPGA Inspired by Biological Systems", Special Issue of JSA on Dependable Parallel Computer Systems, Feb. 1997, pp.719-733
[54] J. Von Neumann, Theory of self-reproducing automata(ed A. W. Burks), University of Illionis, Urbana, 1966
[55] Mitchell M., An Introduction to Genetic Algorithms.Cambridge, MIT Press,1996
[56] J.H. Holland, Adaptation in Natural and Artificial System, The University of Michigan Press, 1975
[57] J D Schaffer. Some Experiments in Machine Learning Using Vector Evaluated GAs. Ph. D. Thesis, Nashville, TN: Vanderbilt University, 1984.
[58] D Goldberg Genetic Algorithms for Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
[59] Fogel D B., Evolving programing for training neural networks,International Joint Conf.. on Neural Networks'90, Washington, D.C., 1990,601-605
[60] Bethke A D. , Genetic algorithms as function optimizers, PH.D.diss., University of Michigan, 1981
[61] IEEE. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press. 2 volumes. 1994.
[62] IEEE. Proceedings of the Second IEEE Conference on Evolutionary Computation. IEEE Press. 2 volumes. 1995.
[62] IEEE. Proceedings of the Third IEEE Conference on Evolutionary Computation. IEEE Press. 1996.
[63] IEEE. Proceedings of the Fourth IEEE Conference on Evolutionary Computation. IEEE Press. 1997
[64] IEEE. Proceedings of the 1998 IEEE Conference on Evolutionary Computation, Anchorage, Alaska, May 4 - 9, 1998. Piscataway, NJ: IEEE. 1 volume. NOTE: This event was part of the 1998 IEEE World Congress on Computational Intelligence. 1998.
[65] IEEE Neural Networks Council (Editor). Proceedings of the 2001 Congress on Evolutionary Computation: Cec2001, May 27-30, COEX Center, Seoul, Korea, IEEE-Press, 2001
[66] IEEE Neural Networks Council. Proceedings of the 2002 Congress on Evolutionary Computation: Hilton, Hawaiian Village Hotel, Honolulu, Hawaii, May 12-17, IEEE-Press, 2002
[67] Ruhul Sarker, Robert Reynolds, Hussein Abbass, Kay Chen Tan, Bob McKay, Daryl Essam, Tom Gedeon Proceedings of the 2003 Congress on Evolutionary Computation: Canberra, Australia, December 8-12, IEEE-Press, 2003
[68] L. Spector, E. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon & E. Burke (Eds), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). San Francisco, CA: Morgan Kaufmann Publishers,
[69] W. B. Langdon, et al. (editors), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2002, San Francisco, CA: Morgan Kaufmann Publishers.
[70] Genetic and Evolutionary Computation—GECCO 2003: Genetic and Evolutionary Computation Conference, Chicago, IL, USA, July 2003, vol. LNCS 2724, Lecture Notes in Computer Science, E. Cantu-Paz, J. A. Foster, K. Deb, L. D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. A. Dowsland, and N. J. J. Miller, Eds. Berlin: Springer-Verlag, 2003,
[71] Zitzler, Eckart, Deb, Kalyanmoy, Thiele, Lothar, Coello Coello, Carlos A., and Corne, David (editors). 2001. Evolutionary Multi-Criterion Optimization, First International Conference, EMO 2001, Zurich, Switzerland, March 2001, Proceedings. Lecture Notes in Computer Science. Volume 1993. Berlin, Germany: Springer-Verlag.
[72] Fonseca, Carlos M., Fleming, Peter J., Zitzler, Eckart, Deb, Kalyanmoy, and Thiele, Lothar (editors). 2003. Evolutionary Multi-Criterion Optimization: Second International Conference, EMO 2003, Faro, Portugal, April 2003 Proceedings. Lecture Notes in Computer Science No. 2632. Berlin: Springer.
[73] Stoica, Adrian, Keymeulen, Didier, and Lohn, Jason (editors). 1999. Proceedings of the First NASA / DOD Workshop on Evolvable Hardware, Pasadena, California, July 19-21, 1999. Los Alamitos, CA. IEEE Computer Society.
[74] Lohn, Jason, Stoica, Adrian, Keymeulen, Didier, and Colombano, Silvano (editors). 2000. Proceedings of the Second NASA / DoD Workshop on Evolvable Hardware, July 13-15 2000, Palo Alto, California. Los Alamitos, CA: IEEE Computer Society Press.
[75] Keymeulen, Didier, Stoica, Adrian, Lohn, Jason, and Zebulum, Ricardo Salem (editors). 2001. Proceedings of the Third NASA/DOD Workshop on Evolvable Hardware, Pasadena, California, July 12-14,2001. Los Alamitos, CA. IEEE Computer Society.
[76] Stoica, Adrian, Lohn, Jason, Katz, Rich, Keymeulen, Didier and Zebulum, Ricardo Salem (editors). 2002. Proceedings of 2002 NASA/DoD Conference on Evolvable Hardware. Los Alamitos, CA: IEEE Computer Society.
[77] Lohn, Jason, Zebulum, Ricardo, Steincamp, James, Keymeulen, Didier, Stoica, Adrian, and Ferguson, Michael I. (editors). 2003. Proceedings of 2003 NASA/DoD Conference on Evolvable Hardware. Los Alamitos, CA: IEEE Computer Society
[78] Cohon, J. L. Multiobjective Programming and Planning. NewYork: Academic Press. David E Goldberg. 1978.
[79] Steuer, R. E. Multiple Criteria Optimization: Theory, Computation, and Applica- tion. New York: Wiley. 1986.
[80] Koski, J. (1984). Multicriterion optimization in structural design. In E. Atrek, R. H. Gallagher, K. M. Ragsdell, and O. C. Zienkiewicz (Eds.), New Directions in Optimum Structural Design, pp. 483C503. Wiley.
[81] Schaffer, J. D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. Ph. D. thesis, Vanderbilt University. Unpublished. 1984.
[82] Schaffer, J. D. Multiple objective optimization with vector evaluated genetic algorithms. In J. J. Grefenstette (Ed.),Proceedings of an International Conference on Ge- netic Algorithms and Their Applications, Pitts-burgh, PA, 1985. pp. 93C100. sponsored by Texas Instruments and U.S. Navy Center for Applied Research in Artificial Intelli- gence (NCARAI).
[83] Hajela, P. and C. Y. Lin. Genetic search strategies in multicriterion optimal design. Structural Optimization 1992, 4, 99C107.
[84] Fonseca, C. M. and P. J. Fleming. Genetic algorithms for multiobjective opti-mization: Formulation, discussion and generalization. In S. Forrest (Ed.), Proceed-ings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993, pp. 416C423. Morgan Kaufmann.
[85] Horn, J. and N. Nafpliotis. Multiobjective optimization using the niched pareto genetic algorithm. IlliGAL Report 93005, Illinois Genetic Algorithms Labo-ratory, University of Illinois, Urbana, Champaign. 1993.
[86] Horn, J., Nafpliotis, N. and Goldberg, D. E. A niched pareto genetic algo-rithm for multiobjective optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Computation, Vol-ume 1, Piscataway, NJ, 1994. pp. 82C87. IEEE.
[87] Srinivas, N. and Deb, K. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 1994,2(3), 221C248.
[88] Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T.. A fast elitist nondom-inated sorting genetic algorithm for multi-objective optimization: NSGAII. In M. S. et al. (Ed.), Parallel Problem Solving from Nature-PPSN VI, Berlin, 2000, pp. 849-858. Springer.
[89] Zitzler, E., Laumanns, M. and Thiele, L.. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103, 2001. ETH Zentrum, Gloriastrasse 35, CH-8092Zurich, Switxerland.
[90] Purshouse, R. C, Fleming, P. J.. The Multi-objective Genetic Algorithm Ap-plied to Benchmark Problems-an Analysis. Research Report No. 796. 2001 Department of Automatic Control and Systems Engineering University of Sheffield, Sheffield, S1 3JD, UK.
[91] Leung, Y. W. and Zhang, Q.. Evolutionary algorithms + experimenta design methods: A hybrid apprpach for hard optimization and search problems, Res. Grant Proposal, Hong Kong Baptist Univ. 1997.
[92] Wu, Q.. On the optimality of orthogonal experimental design. Acta Math Appl Sinica, 1978, vol. 1, no. 4, pp. 283-299.
[93] Leung, Y. W. and Wang, Y.. An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Trans. Evol. Comput. 2001, vol.5, No.1, pp. 40-53.
[94] Montgomery, D. C. Design and Analysis of Experiments. 3rd ed. 1991, New York: Wiley. [95] Hick, C. R. (1993). Fundamental Concepts in the Design of Experiments. 4th ed. TX: Saunders College Publishing.
[96] Zitzler, E.(1999). Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph. D. thesis, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland. TIK-Schriftenreihe Nr. 30, Diss ETH No. 13398, Shaker Verlag, Aachen, Germany
[97] M. Elad, A. Tal, and S. Ar. Content Based Retrieval of VRML Objects-An Iterative and Interactive Approach. 6th Eurographics Workshop in Multimedia, pp. 107-118,2001.
[98] Fakir S. N. and Greg T. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Transactions on Visualization and Computer Graphics, vol. 9, no. 2, pp. 191-205,2003.
[99] Fang S. F and Chen H. Hardware Accelerated Voxelization. Computer&Graphics, vol. 24, no. 3,433-442, 2000.
[100] 郭涛.演化计算与优化[博士学位论文].武汉:武汉大学.1999.P37-52.