Computer Industry Laboratory

Lothar M. Schmitt Associate Professor	Incheon Paik Assistant Professor

Research by faculty and students in the Computer Industry Laboratory was carried out in the fields E-Commerce, UNIX Applications, Genetic Algorithms and Optimization, Artificial Intelligence, Physics and Mathematics. Several articles were published as book chapters, journal-contributions, proceedings-contributions in conferences, and technical reports. Some work is under review in the publication process. The Computer Industry Laboratory is cooperating with other labs in regard to robotics research and students can do applied work in this area under Computer Industry Laboratory faculty supervision.

Refereed Journal Papers

[lothar-01:2004]	Lothar M. Schmitt. Theory of Genetic Algorithms II - Models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling. Theoretical Computer Science, pages 181-231, 2004.
	Rank 3 among all papers in all volumes of Theo. Comp. Sci. in regard to downloads during 1-8, 2004 from the Elsevier website (L.M. Schmitt also holds the Rank 1 paper). We present a short setup for an asymptotically converging, scaled genetic algorithm which employs an arbitrary-size alphabet. The alphabet is primarily interpreted as a set of equidistant real numbers, and multiplespot mutation performs a scalable compromise between pure random search and neighborhood-based change on the alphabet level. We discuss various versions of the crossover operator, in particular, uniform crossover and gene-lottery crossover which does not commute with mutation. The Vose-Liepins version of mutation-crossover is also integrated in our approach. In order to achieve convergence to global optima, the mutation rate and the crossover rate have to be annealed to zero in proper fashion, and unbounded, power-law scaled proportional fitness selection is used with logarithmic growth in the exponent. Our analysis shows that using certain specific types of crossover operation and large population size allows for particularly slow annealing schedules for the crossover rate. In our discussion, we focus on the following three major aspects based upon contraction properties of the mutation and fitness selection operators: (i) The drive towards uniform populations in a genetic algorithm using standard operations. (ii) Weak ergodicity of the inhomogeneous Markov chain describing the probabilistic model for the scaled algorithm. (iii) Convergence to globallly optimal solutions. In particular, we remove two restrictions imposed in Theorem 8.6 and Remark 8.7 of [Theo. Comp. Sci. 259(2001), 1-61]wherea similar type of algorithm is considered as described here: mutation need notcommute with crossover, and the fitness function need not have a single maximum.
[paikic-01:2004]	Incheon Paik and Wonhee Park. Software Component Architecture for an Information Infrastructure to Support Innovative Product Design in a Supply Chain. Journal of Organization Computing and Electronic Commerce, Lawrence Erlbaum Associates, 15(2):105-136, 2005.
	Existing methodologies to increase the efficiency of design in supply chain management(SCM) process consider cost, quality, function, and technology attributes separately. However, there is no integrated information infrastructure to consider these attributes together. We have devised new table structures to combine the four attributes and their relationships organically. Simple ontology concepts for this information infrastructure, considering the supply chain tree and the structure of attribute-relationship tables, with some restriction from general ontology, were introduced. Basic database schemas using the designed ontology were created for the information infrastructure for SCM collaboration. A software component architecture that provides interface services to clients and other business logic was also developed, based on this information infrastructure and using the component-based software development (CBSD) methodology. We built Servlet classes forWeb presentation, and used Enterprise JavaBeans(EJB)Entity Beans and Session Beans for business logic. Examples to demonstrate our information infrastructure were also described. Experiments using the three platforms provide performance data that show the capability of our server-side software component system.

Referred Proceeding Papers

[lothar-02:2004]	Lothar M. Schmitt. Classification with Scaled Genetic Algorithms in a Coevolutionary Setting. In Riccardo Poli et al (chairs), editor, Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2004. Lecture Notes in Computer Science., pages 138-149, Berlin, Germany, 2004. ISGEC, Springer Verlag.
	This work discusses asymptotic convergence of scaled genetic algorithms in a coevolutionary setting where the under lying population contains fixed numbers of creatures of various types. These types of creatures can act on each other in cooperative or competitive manner. The genetic algorithm uses common mutation and crossover operators as well as proportional fitness selection. By a scaled genetic algorithm, we mean that the mutation and crossover rates have to be annealed to zero in proper fashion over the course of the algorithm, and power-lawscaling is used for the fitness function with (unbounded) logarithmic growth in the exponent. In the case that a scaled genetic algorithm is used as function optimizer, it has been shown [Theoret. Comput. Sci. 310, p. 181] that such an algorithm is able to find global optima asymptoticly with probability one. However, in the case of a coevolutionary setting, global optima need not exist. Based upon a properly defined, population-dependent fitness function, the set of creatures of a specific type can be canonically grouped into equivalence classes such that all members of one equivalence class are either inferior or superior to all members of another class. We show that in the situation of a coevolutionary setting, a scaled genetic algorithm at least retains the property of converging to a probability distribution over such populations that contain only copies of one creature from the top-class for every or a selected group of types while on the other hand maintaining a noisy field of test-cases.
[lothar-03:2004]	Lothar M. Schmitt and Stefan Droste. Feasible Approaches to Convergence Results for Evolutionary Algorithms - Part I: Introductory overview and analysis of scaled genetic algorithms. In Riccardo Poli et al (conf. chairs). A. Wright et al (ws. organizers), editor, Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2004. (Workshop on Evolutionary Computation Theory, refereed)., pages 1-12, Berlin, Germany, 2004. ISGEC, Springer Verlag.
	Despitemany successes of evolutionary algorithms(EAs) in real-world applications, theoretical knowledge in regard to these algorithms is still in its infancy. In this work, we discuss a number of approaches to theory for EAs in regard to strengths and weaknesses of statements for convergence-speed obtained with these methods. This includes the general convergence-analysis of a broad class of EAs in an arbitrary-fitness-function black-box scenario similar to the setting for the simulated annealing algorithm, and the runtime-analysis of specific EAs on limited classes of fitness-functions within the framework of asymptotic runtime-analysis for randomized algorithms. We propose that a suitable merger of ideas put forward through the latter two types of convergence-analysis may yield substantial progress towards understanding convergence behavior of EAs. In particular, this may yield a unified theoretical framework for EAs as well as probabilistic estimates for runtimes of EAs used in real-world applications.
[lothar-04:2004]	Stefan Droste and Lothar M. Schmitt. Feasible Approaches to Convergence Results for Evolutionary Algorithms - Part II: Runtime analysis of evolutionary algorithms andsummary. In Riccardo Poli et al (conf. chairs). A. Wright et al (ws. organizers), editor, Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2004. (Workshop on Evolutionary Computation Theory, refereed)., pages 1-12, Berlin, Germany, 2004. ISGEC, Springer Verlag.
	(See above). Despite many successes of evolutionary algorithms (EAs) in real-world applications, theoretical knowledge in regard to these algorithms is still in its infancy. In this work, we discuss a number of approaches to theory for EAs in regard to strengths and weaknesses of statements for convergence-speed obtained with these methods. This includes the general convergence- analysis of a broad class of EAs in an arbitrary-fitness-function black-box scenario similar to the setting for the simulated annealing algorithm, and the runtime-analysis of specific EAs on limited classes of fitness-functions within the framework of asymptotic runtime-analysis for randomized algorithms. We propose that a suitable merger of ideas put forward through the latter two types of convergence-analysis may yield substantial progress towards understanding convergence behavior of EAs. In particular, this may yield a unified theoretical framework for EAs as well as probabilistic estimates for runtimes of EAs used in real-world applications.
[paikic-02:2004]	Incheon Paik, H. Akimoto, and S. Takami. Automating Design Support in Supply Chains on Semantic Web Services. In D. Schwabe, editor, Proceedings of the WWW2004 Workshop on Application Design, Development and Implementation Issues in the Semantic Web, page Web Version, New York, U.S.A, May 2004. WWW 2004 Workshop Committee, CEURWorkshop Publish.
[paikic-03:2004]	T. Hossain and I. Paik. Automated Business Process Choreography for Business Transaction and Negotiation in B2B Collaboration. In HC Committee, editor, Proceedings of Seventh International Conference on Human & Computer, pages 47-51, Aizu-Wakamatu, Fukushima, Japan, September 2004. Univ. of Aizu, HC committee.
[paikic-04:2004]	I. Paik, Md. S. Hossain, and Md. T. Hossain. Automating Business Transaction and Negotiation in Supply Chaines UsingWeb Service Composition. In D. Wei and Q. Jin, editors, Proceedins of CIT 2004 Conference, Wuhan China, September 2004. Univ. of Aizu and Wuhan Univ., CIT 2004 committee.
[paikic-05:2004]	D. Maruyama, I. Paik, and Y. Watanabe. Toward a Multi-Mobile Agent System on Semantic Web Service: Design Support in Supply Chain. In Shi-Kuo Chang, editor, Proceedins of DMS 2004 Conference, pages 181-185, KSI Graduate School, Skokie, IL, U.S.A, September 2004. DMS 2004 Committee, Knowledge System Institute.
[paikic-06:2004]	I. Paik, S. Takami, and Y. Watanabe. Autonomous Agent to Support Design in Supply Chain Based on Semantic Web Service. In etc. M. Ishikawa, editor, Proceedings of Int. Conf. of Hybrid Intellisgent System, pages 254-269, Kitakyushu, Japan, December 2004. HIS 2004 Committee, IEEE Computer Society.

Unreferred Papers

[lothar-05:2004]	Lothar M. Schmitt. De Jong's Challenge for Coevolutionary Genetic Algorithms. In H.-G. Beyer et al, editor, Proceedings of the Dagstuhl Seminar 04081: Theory of Evolutionary Algorithms., page accepted, Schloss Dagstuhl, Saarland, Germany, 2004. Max-Planck Society, Max-Planck Institute for Computer Science Conference Center.
	The written contribution to the Proceedings of the Dagstuhl Seminar 04081 is an extension of theGECCO2004 contribution of L.M. Schmitt. It contains additional examples for the setting under consideration, and a detailed collection of proofs which could not be added to theGECCO2004 publication due to length-of-submission limitations.

Chapters in Book

[lothar-06:2004]

Lothar M. Schmitt. Asymptotic Convergence of Scaled Genetic Algorithms to Global Optima - A gentle introduction to the theory., pages 157-200. Number 11 in Genetic Algorithms And Evolutionary Computation Series (D.E. Goldberg, ed.). Kluwer Publishers, Boston, MA, USA, 2004.

The invited book chapter discusses elements of journal articles listed above with an additional mathematical framework. In addition, an outlook on future research activities is given. Altogether, we present a self-contained theoretical framework for a scaled genetic algorithm which converges asymptotically to global optima as anticipated byDavis and Principe in analogy to simulated annealing. We employ the two most common and most simple mixing operators: multiple-bit mutation and single-cut-point crossover. In addition, power-law scaled proportional fitness selection is used based upon an arbitrary fitness function. To achieve asymptotic convergenceto *globaloptima*, mutation and crossoverrates have tobe annealed to zero in proper fashion, and power-law scaling is used with logarithmic growth in the exponent. Our analysis shows that a large population size allows for a particularly slow annealing schedule for crossover.A detailed listing of theoretical aspects is presented including (i) prerequisites on inhomogeneous Markov chains; (ii) the drive towards uniform populations in a genetic algorithm; (iii) weak and strong ergodicity of the inhomogeneous Markovchain describing the probabilistic model for the scaled algorithm; (iv) convergenceto globally optimal solutions. We discuss various generalizations and extensions of the framework such as larger alphabets or other versions of the mutation-crossover operator, in particular, the Vose-Liepins version of mutation-crossover. This refers to recent work by the author in [Theo. Comp. Sci. 259 (2001), 1-61, 310 (2004), 181-231] where similar types of algorithms are considered over an arbitrary-size alphabet and convergence for arbitrary fitness function to global optima under more general conditions is shown.

Academic Activities

[paikic-07:2004]

Incheon Paik, Sep. 2004. Program Committee, PC Member, the 4th International Conference on Computer and Information Technology (CIT2004)

Ph.D. and Other Theses

[paikic-08:2004]	Ken Nariai. Master Thesis: Planning and Composition of Web Services for Dynamic Constraints Using Situation Calculus, Graduate School, University of Aizu, 2004. Thesis Advisor: I. Paik
[paikic-09:2004]	Yuuki Ooishi. Master Thesis: Ontology Querying System with Process of Rules onSemantic Web, Graduate School, University of Aizu, 2004. Thesis Advisor: I. Paik
[paikic-10:2004]	Yuu Watanabe. Graduation Thesis: Intelligent Web Service for Dynamic Constraints using Semantic Web Rule, Graduate School, University of Aizu, 2004. Thesis Advisor: I. Paik
[paikic-11:2004]	Katsuaki Endo. Graduation Thesis: Architecture for Intelligent Web Service Using Rules: Trip Planning Case, University of Aizu, 2004. Thesis Advisor: I. Paik
[paikic-12:2004]	Yuki Kurita. Graduation Thesis: Design of Software Component for Intelligent Semantic Web Service, University of Aizu, 2004. Thesis Advisor: I. Paik
[paikic-13:2004]	Mitsuteru Shinozawa. Graduation Thesis: Infrastructure of Intelligent Web Service Environment for Dynamic Constraint using Situation Calculus, University of Aizu, 2004. Thesis Advisor: I. Paik

Others

[lothar-07:2004]

Renu Gupta) Lothar M. Schmitt (John Brine. Developement of online interactive teaching systems for English, Computer Science and Mathemetics education. Code available from L.M. Schmitt. Paper in preparation., 2004-5.

Ongoing project currently running in four courses at The University of Aizu with three faculty. Based upon: Pedagogical aspects of a UNIX-based network management system for English instruction, Lothar M. Schmitt and Kiel T. Christianson (authors). System 26, (1998), 567-589 (refereed journal). We have developed a UNIX-based management system which supports the instructor in teaching English as a second language using a network of workstations. The present implementation is aimed at teaching English composition and Discrete Systems to Japanese students at The University of Aizu. The system has a convenient setup mechanism designed to assist, in particular, the computer novice. While running, the system takes care of the following tasks using the cron mechanism of UNIX: assignments are sent out via e-mail on preset dates; if necessary, students are reminded of missing homework; homework sent back by students via e-mail is sorted in regard to course, section and assignment; submission deadlines and required length of the homework are enforced; homework is partially evaluated in regard to mechanical mistakes such as spelling or punctuation; quizzes are automatically evaluated; results of the evaluations by the machine are sent back to the students automatically (to trigger resubmission); the writings of students are reformatted to make human correction easier; the use of global or specialized vocabulary can be measured for individual students as well as classes; authentic, interesting or critical examples of grammatical patterns can be identified and collected for presentation in class or research purposes; desired statistical evidence is generated; and graphical display of data is generated.

2006 THE UNIVERSITY OF AIZU ALL RIGHTS RESERVED