{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T15:32:42Z","timestamp":1758814362326,"version":"3.32.0"},"reference-count":22,"publisher":"ASME International","issue":"1","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2005,3,1]]},"abstract":"<jats:p>This paper presents a new method to isomorphism identification based on two novel evolutionary approaches\u2014ant algorithm (AA) and artificial immune system (AIS). Salient features of the two evolutionary approaches are their efficient, robust and general-purpose algorithms for isomorphism identification despite its nondeterministic polynomial (NP) hard nature. First, based on the rearrangement of the vertexes in kinematic chains, the isomorphism identification of kinematic chains is transformed into a degree-reducible traveling salesman problem (TSP), so that the dimension and complexity can be largely decreased. Then AA and AIS algorithms are adopted to solve the transformed TSP. At last, characteristics of the two evolutionary approaches are discussed based on case studies.<\/jats:p>","DOI":"10.1115\/1.1846057","type":"journal-article","created":{"date-parts":[[2005,3,14]],"date-time":"2005-03-14T23:02:33Z","timestamp":1110841353000},"page":"18-24","update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":16,"title":["Isomorphism Identification of Kinematic Chains Using Novel Evolutionary Approaches"],"prefix":"10.1115","volume":"5","author":[{"given":"Renbin","family":"Xiao","sequence":"first","affiliation":[{"name":"CAD Center, Huazhong University of Science and Technology, Wuhan, Hubei, 430074, People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenwu","family":"Tao","sequence":"additional","affiliation":[{"name":"CAD Center, Huazhong University of Science and Technology, Wuhan, Hubei, 430074, People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Liu","sequence":"additional","affiliation":[{"name":"CAD Center, Huazhong University of Science and Technology, Wuhan, Hubei, 430074, People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2005,3,14]]},"reference":[{"unstructured":"Zhang, W. J., 1991, \u201cAn Object-Oriented Mechanism Definition and Description With a Genetic Mechanism Model,\u201d Technical Report No. BM-1.91, TU Delft, The Netherlands.","key":"2019100611070297500_r1"},{"doi-asserted-by":"crossref","unstructured":"Zhang, W. J., and Breteler, A. J., 1996, \u201cAn Approach to Mechanism Topology Identification With Consideration of Design Progression,\u201d J. Mech. Eng. Sci., 211(3), pp. 175\u2013183.","key":"2019100611070297500_r2","DOI":"10.1243\/0954406971521755"},{"doi-asserted-by":"crossref","unstructured":"Shin, J. K., and Krishnamurty, S., 1994, \u201cOn Identification and Canonical Numbering of Pin-Jointed Kinematic Chains,\u201d ASME J. Mech. Des., 116(1), pp. 182\u2013188.","key":"2019100611070297500_r3","DOI":"10.1115\/1.2919344"},{"doi-asserted-by":"crossref","unstructured":"Kobler, J., Schoning, U. J., and Toran, J., 1993, The Graph Isomorphism Problems: Its Structural Complexity, Birkhauser, Boston.","key":"2019100611070297500_r4","DOI":"10.1007\/978-1-4612-0333-9"},{"doi-asserted-by":"crossref","unstructured":"Tischler, C. R., Samual, A. E., and Hunt, K. H., 1995, \u201cKinematic Chain for Robot Hands\u20141. Orderly Number-Synthesis,\u201d Mech. Mach. Theory, 30(8), pp. 1193\u20131215.","key":"2019100611070297500_r5","DOI":"10.1016\/0094-114X(95)00043-X"},{"unstructured":"Davis, L., 1991, Handbook of Genetic Algorithms, Van Nostrand Reinbold, New York.","key":"2019100611070297500_r6"},{"unstructured":"Zhou, J., Cha, J. Z., and Xiao, R. B., 1998, Intelligent Design, Higher Education Press, Beijing (in Chinese).","key":"2019100611070297500_r7"},{"doi-asserted-by":"crossref","unstructured":"Bonabeau, E., Dorigo, M., and Theraulaz, G., 2000, \u201cInspiration for Optimization From Social Insect Behavior,\u201d Nature (London), 6, pp. 39\u201342.","key":"2019100611070297500_r8","DOI":"10.1038\/35017500"},{"unstructured":"Xiao, R. B., and Wang, L., 2002, \u201cArtificial Immune System: Principle, Models, Analysis and Perspectives,\u201d Chin. J. Comput., 25(12), pp. 1281\u20131293.","key":"2019100611070297500_r9"},{"doi-asserted-by":"crossref","unstructured":"Dobrjanskyi, L., and Freudenstein, F., 1989, \u201cSome Applications of Group Theory to the Enumeration and Structural Analysis of Basic Kinematic Chains,\u201d ASME J. Mech., Transm., Autom. Des., 111, pp. 494\u2013497.","key":"2019100611070297500_r10","DOI":"10.1115\/1.3259027"},{"unstructured":"Wilson, R., 1972, Introduction to Graph Theory, 3rd ed., Longman, London.","key":"2019100611070297500_r11"},{"doi-asserted-by":"crossref","unstructured":"Gambardella, L. M., and Dorigo, M., 1996, \u201cSolving Symmetric and Asymmetric TSPs by Ant Colony,\u201d Proceedings of the IEEE Conference on Evolution Computation, IEEE Press, New York, pp. 622\u2013627.","key":"2019100611070297500_r12","DOI":"10.1109\/ICEC.1996.542672"},{"doi-asserted-by":"crossref","unstructured":"Dorigo, M., and Gambardella, L. M., 1997, \u201cAnt Colony System: a Cooperative Learning Approach to Traveling Salesman Problem,\u201d IEEE Trans. Evol. Comput., 1(1), pp. 73\u201381.","key":"2019100611070297500_r13","DOI":"10.1109\/4235.585892"},{"doi-asserted-by":"crossref","unstructured":"Xiao, R. B., and Tao, Z. W., 2003, \u201cCo-Evolutionary Ant Algorithm and Application in Multi-Objective Optimization Problems,\u201d ASME 2003 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, ASME, Chicago, IL, DETC2003\/CIE-48258.","key":"2019100611070297500_r14","DOI":"10.1115\/DETC2003\/CIE-48285"},{"doi-asserted-by":"crossref","unstructured":"Dorigo, M., Bonabeau, E., and Theraulaz, G., 2000, \u201cAnt Algorithms and Stigmergy,\u201d Future Generation Comput. Syst., 16, pp. 851\u2013871.","key":"2019100611070297500_r15","DOI":"10.1016\/S0167-739X(00)00042-X"},{"doi-asserted-by":"crossref","unstructured":"Xiao, R. B., He, J. H., Chang, M., and Shi, H. M., 2001, \u201cAn Ant Algorithm Approach to the Isomorphism Identification of Mechanism Kinematic Chains,\u201d ASME 2001 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, ASME, Pittsburgh, PA, DETC2001\/CIE21674.","key":"2019100611070297500_r16","DOI":"10.1115\/DETC2001\/CIE-21674"},{"doi-asserted-by":"crossref","unstructured":"Endoh, S., Toma, N., and Yamada, K., 1998, \u201cImmune Algorithm for n-TSP,\u201d Proc. of 1998 IEEE International Conference on Systems, Man, and Cybernetics, San Diego, CA, pp. 3844\u20133849.","key":"2019100611070297500_r17","DOI":"10.1109\/ICSMC.1998.726687"},{"doi-asserted-by":"crossref","unstructured":"Chun, J. S., Kim, M. K., and Jung, H. K., 1997, \u201cShape Optimization of Electromagnetic Devices Using Immune Algorithm,\u201d IEEE Trans. Magn., 33(2), pp. 1876\u20131879.","key":"2019100611070297500_r18","DOI":"10.1109\/20.582650"},{"doi-asserted-by":"crossref","unstructured":"Huang, S. J. , 2000, \u201cAn Immune Based Optimization Method to Capacitor Placement in a Radial Distribution System,\u201d IEEE Trans. Power Deliv., 15(2), pp. 744\u2013749.","key":"2019100611070297500_r19","DOI":"10.1109\/61.853014"},{"doi-asserted-by":"crossref","unstructured":"Xiao, R. B., Wang, L., and Fan, Z., 2002, \u201cAn Artificial Immune System Based Isomorphism Identification Method for Mechanism Kinematic Chains,\u201d ASME 2002 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, ASME, Montreal, Canada, DETC2002\/DAC-34063.","key":"2019100611070297500_r20","DOI":"10.1115\/DETC2002\/DAC-34063"},{"doi-asserted-by":"crossref","unstructured":"Mruthyunjaya, T. S., and Balasubramanzan, H. R., 1987, \u201cIn Quest of a Reliable and Efficient Computational Test for Detection of Isomorphism in Kinematic Chains,\u201d Mech. Mach. Theory, 22(2), pp. 131\u2013140.","key":"2019100611070297500_r21","DOI":"10.1016\/0094-114X(87)90036-X"},{"unstructured":"Grefenstette, J., Gopal, R., and Gucht, D. V., 1985, \u201cGenetic Algorithms for the Traveling Salesman Problem,\u201d Proc. of 1st Int. Conf. On Genetic Algorithms and Their Applications, Law Erlbaum, Hillsdale, NJ, pp. 160\u2013168.","key":"2019100611070297500_r22"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/5\/1\/18\/5773765\/18_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/5\/1\/18\/5773765\/18_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,26]],"date-time":"2024-12-26T23:25:12Z","timestamp":1735255512000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/5\/1\/18\/449196\/Isomorphism-Identification-of-Kinematic-Chains"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.1846057","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2005,3,1]]}}}