Researcher Profile and Settings

Affiliation

• Information Initiative Center　Systems Design

Job Title

• Professor

Degree

• PhD（Hokkaido university）

URL

https://www.iic.hokudai.ac.jp/

ORCID ID

•  https://orcid.org/0000-0002-5750-9217

J-Global ID

• 200901037594718436

Research Interests

• Cloud computing   並列分散処理   システム設計   進化計算   Parallel and distributed processing   Systems design   Evolutionary computation   

Research Areas

• Informatics / Information networks
• Informatics / Computer systems
• Informatics / High-performance computing
• Informatics / Intelligent informatics
• Informatics / Software
• Informatics / Sensitivity (kansei) informatics
• Informatics / Soft computing

Educational Organization

•  Bachelor's degree program　School of Engineering
•  Master's degree program　Graduate School of Information Science and Technology
•  Doctoral (PhD) degree program　Graduate School of Information Science and Technology

Academic & Professional Experience

• 2024/04 - Today Hokkaido University Vice Executive Director
• 2024/04 - Today Hokkaido University ICT Promotion Office Vice Director
• 2019/04 - Today Hokkaido University Education and Research Council Councillor
• 2019/04 - Today 北海道大学 情報環境推進本部 情報化推進室長
• 2019/04 - Today Hokkaido University Information Initiative Center Director
• 2015/10 - Today 国立情報学研究所 客員教授
• 2012/08 - Today Hokkaido university Professor
• 2013/04 - 2019/03 Hokkaido University Information Initiative Center Vice director
• 2007/04 - 2012/07 Hokkaido university Associate professor
• 2007 - 2009 国立情報学研究所 客員准教授
• 1999/10 - 2007/03 Hokkaido university Associate professor
• 1996/04 - 1999/09 Hokkaido university Instructor
• 1998/06 - 1999/03 University of Illinois at Urbana-Champaign Visiting scholar

Association Memberships

• The Japanese society for evolutionary computation   米国電気電子学会   情報処理学会   IEEE   Information processing society of Japan   

Research Activities

Published Papers

• Learning from the Past Training Trajectories: Regularization by Validation.

  Enzhi Zhang, Mohamed Wahib, Rui Zhong, Masaharu Munetomo

  J. Adv. Comput. Intell. Intell. Informatics 28 (1) 67 - 78 2024/01
• Q-learning based vegetation evolution for numerical optimization and wireless sensor network coverage optimization

  Rui Zhong, Fei Peng, Jun Yu, Masaharu Munetomo

  Alexandria Engineering Journal 87 148 - 163 1110-0168 2024/01 

  Vegetation evolution (VEGE) is a newly proposed meta-heuristic algorithm (MA) with excellent exploitation but relatively weak exploration capacity. We thus focus on further balancing the exploitation and the exploration of VEGE well to improve the overall optimization performance. This paper proposes an improved Q-learning based VEGE, and we design an exploitation archive and an exploration archive to provide a variety of search strategies, each archive contains four efficient and easy-implemented search strategies. In addition, online Q-Learning, as well as ε-greedy scheme, are employed as the decision-maker role to learn the knowledge from the past optimization process and determine the search strategy for each individual automatically and intelligently. In numerical experiments, we compare our proposed QVEGE with eight state-of-the-art MAs including the original VEGE on CEC2020 benchmark functions, twelve engineering optimization problems, and wireless sensor networks (WSN) coverage optimization problems. Experimental and statistical results confirm that the proposed QVEGE demonstrates significant enhancements and stands as a strong competitor among existing algorithms. The source code of QVEGE is publicly available at https://github.com/RuiZhong961230/QVEGE.
• Surrogate Ensemble-Assisted Hyper-Heuristic Algorithm for Expensive Optimization Problems

  Rui Zhong, Jun Yu, Chao Zhang, Masaharu Munetomo

  International Journal of Computational Intelligence Systems 16 (1) 1875-6891 2023/12 

  This paper proposes a novel surrogate ensemble-assisted hyper-heuristic algorithm (SEA-HHA) to solve expensive optimization problems (EOPs). A representative HHA consists of two parts: the low-level and the high-level components. In the low-level component, we regard the surrogate-assisted technique as a type of search strategy and design the four search strategy archives: exploration strategy archive, exploitation strategy archive, surrogate-assisted estimation archive, and mutation strategy archive as low-level heuristics (LLHs), each archive contains one or more search strategies. Once the surrogate-assisted estimation archive is activated to generate the offspring individual, SEA-HHA first selects the dataset for model construction from three principles: All Data, Recent Data, and Neighbor, which correspond to the global and the local surrogate model, respectively. Then, the dataset is randomly divided into training and validation data, and the most accurate model built by polynomial regression (PR), support vector regression (SVR), and Gaussian process regression (GPR) cooperates with the infill sampling criterion is employed for solution estimation. In the high-level component, we design a random selection function based on the pre-defined probabilities to manipulate a set of LLHs. In numerical experiments, we compare SEA-HHA with six optimization techniques on 5-D, 10-D, and 30-D CEC2013 benchmark functions and three engineering optimization problems with only 1000 fitness evaluation times (FEs). The experimental and statistical results show that our proposed SEA-HHA has broad prospects for dealing with EOPs.
• An evolutionary robotics approach to a multi-legged robotic swarm in a rough terrain environment

  Daichi Morimoto, Haruhi Tsukamoto, Motoaki Hiraga, Kazuhiro Ohkura, Masaharu Munetomo

  Artificial Life and Robotics 28 (4) 661 - 668 1433-5298 2023/11 

  This paper demonstrates a controller design of a multi-legged robotic swarm in a rough terrain environment. Many studies in swarm robotics are conducted with mobile robots that work in relatively flat fields. This paper focuses on a multi-legged robotic swarm, which is expected to operate not only in a flat field but also in rough terrain environments. However, designing a robot controller becomes a challenging problem because a designer has to consider how to coordinate a large number of joints in a robot, besides the complexity of a swarm problem. This paper employed an evolutionary robotics approach for the automatic design of a robot controller. The experiments were conducted by computer simulations with the path formation task. The results showed that the proposed approach succeeds in generating collective behavior in flat and rough terrain environments.
• Vegetation Evolution with Dynamic Maturity Strategy and Diverse Mutation Strategy for Solving Optimization Problems

  Rui Zhong, Fei Peng, Enzhi Zhang, Jun Yu, Masaharu Munetomo

  Biomimetics 8 (6) 2023/10 

  We introduce two new search strategies to further improve the performance of vegetation evolution (VEGE) for solving continuous optimization problems. Specifically, the first strategy, named the dynamic maturity strategy, allows individuals with better fitness to have a higher probability of generating more seed individuals. Here, all individuals will first become allocated to generate a fixed number of seeds, and then the remaining number of allocatable seeds will be distributed competitively according to their fitness. Since VEGE performs poorly in getting rid of local optima, we propose the diverse mutation strategy as the second search operator with several different mutation methods to increase the diversity of seed individuals. In other words, each generated seed individual will randomly choose one of the methods to mutate with a lower probability. To evaluate the performances of the two proposed strategies, we run our proposal (VEGE + two strategies), VEGE, and another seven advanced evolutionary algorithms (EAs) on the CEC2013 benchmark functions and seven popular engineering problems. Finally, we analyze the respective contributions of these two strategies to VEGE. The experimental and statistical results confirmed that our proposal can significantly accelerate convergence and improve the convergence accuracy of the conventional VEGE in most optimization problems.
• A Hierarchical Cooperative Coevolutionary Approach to Solve Very Large-Scale Traveling Salesman Problem.

  Rui Zhong, Enzhi Zhang, Masaharu Munetomo

  OLA 74 - 84 2023
• Cooperative coevolutionary differential evolution with linkage measurement minimization for large-scale optimization problems in noisy environments

  Rui Zhong, Enzhi Zhang, Masaharu Munetomo

  COMPLEX & INTELLIGENT SYSTEMS 2199-4536 2023/01 

  Many optimization problems suffer from noise, and the noise combined with the large-scale attributes makes the problem complexity explode. Cooperative coevolution (CC) based on divide and conquer decomposes the problems and solves the sub-problems alternately, which is a popular framework for solving large-scale optimization problems (LSOPs). Many studies show that the CC framework is sensitive to decomposition, and the high-accuracy decomposition methods such as differential grouping (DG), DG2, and recursive DG (RDG) are extremely sensitive to sampling accuracy, which will fail to detect the interactions in noisy environments. Therefore, solving LSOPs in noisy environments based on the CC framework faces unprecedented challenges. In this paper, we propose a novel decomposition method named linkage measurement minimization (LMM). We regard the decomposition problem as a combinatorial optimization problem and design the linkage measurement function (LMF) based on Linkage Identification by non-linearity check for real-coded GA (LINC-R). A detailed theoretical analysis explains why our proposal can determine the interactions in noisy environments. In the optimization, we introduce an advanced optimizer named modified differential evolution with distance-based selection (MDE-DS), and the various mutation strategy and distance-based selection endow MDE-DS with strong anti-noise ability. Numerical experiments show that our proposal is competitive with the state-of-the-art decomposition methods in noisy environments, and the introduction of MDE-DS can accelerate the optimization in noisy environments significantly.
• Cooperative Coevolutionary NSGA-II with Linkage Measurement Minimization for Large-Scale Multi-objective Optimization.

  Rui Zhong, Masaharu Munetomo

  EMO 43 - 55 2023
• Generating collective behavior of a multi-legged robotic swarm using an evolutionary robotics approach

  Daichi Morimoto, Motoaki Hiraga, Naoya Shiozaki, Kazuhiro Ohkura, Masaharu Munetomo

  Artificial Life and Robotics 27 (4) 751 - 760 1433-5298 2022/11 

  This paper demonstrates to generate a collective behavior of a multi-legged robotic swarm based on the evolutionary robotics approach. Most studies in swarm robotics are conducted using mobile robots driven by wheels. This paper focuses on generating collective behavior using a multi-legged robotic swarm. The evolutionary robotics approach is employed for designing a robot controller. The intuition-based constraint factors are incorporated into the fitness function to make the gait of robots similar to natural organisms. The experiment on a task of forming a line is conducted in computer simulations using the PyBullet physics engine. The robot controller is represented by a recurrent neural network with a single hidden layer. The experimental results show that proposed constraint factors successfully designed the robot’s gait similar to natural organisms. The results also show that the evolutionary robotics approach successfully designed the robot controller for collective behavior of a multi-legged robotic swarm.
• Generating collective behavior of a multi-legged robotic swarm using an evolutionary robotics approach

  Daichi Morimoto, Motoaki Hiraga, Naoya Shiozaki, Kazuhiro Ohkura, Masaharu Munetomo

  ARTIFICIAL LIFE AND ROBOTICS 27 (4) 751 - 760 1433-5298 2022/11 

  This paper demonstrates to generate a collective behavior of a multi-legged robotic swarm based on the evolutionary robotics approach. Most studies in swarm robotics are conducted using mobile robots driven by wheels. This paper focuses on generating collective behavior using a multi-legged robotic swarm. The evolutionary robotics approach is employed for designing a robot controller. The intuition-based constraint factors are incorporated into the fitness function to make the gait of robots similar to natural organisms. The experiment on a task of forming a line is conducted in computer simulations using the PyBullet physics engine. The robot controller is represented by a recurrent neural network with a single hidden layer. The experimental results show that proposed constraint factors successfully designed the robot's gait similar to natural organisms. The results also show that the evolutionary robotics approach successfully designed the robot controller for collective behavior of a multi-legged robotic swarm.
• Report on Open Space Discussion 2021

  能島, 裕介, 高木, 英行, 棟朝, 雅晴, 濱田, 直希, 西原, 慧, 高玉, 圭樹, 佐藤, 寛之, 桐淵, 大貴, 宮川, みなみ

  進化計算学会論文誌 進化計算学会 13 (1) 1 - 9 2185-7385 2022/07/13 

  This paper is a report on Open Space Discussion (OSD) held in Evolutionary Computation Symposium 2021. The purpose of OSD is to share and discuss problems at hand and future research targets related to evolutionary computation. Discussion topics are voluntarily proposed by some of the participants, and other participants freely choose one to join in the discussion. Through free discussions based on the open space technology framework, it is expected that participants will have new research ideas and start some collaborations. This paper gives the concept of OSD and introduces six topics discussed this year. This paper also shows the responses to the questionnaire on OSD for future discussions, collaborations, and related events.
• Generating and Analyzing Collective Step-Climbing Behavior in a Multi-legged Robotic Swarm

  Daichi Morimoto, Motoaki Hiraga, Kazuhiro Ohkura, Masaharu Munetomo

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13491 LNCS 324 - 331 0302-9743 2022 

  This paper focuses on generating and analyzing collective step-climbing behavior in a multi-legged robotic swarm. The multi-legged robotic swarm is expected to climb obstacles that are hard for a single robot by using other robots as stepping stones. However, designing a robot controller for a multi-legged robotic swarm becomes a challenging problem because it designs not only a gait for the basic movement of robots but also the behavior of robots to exhibit collective behavior. This paper employs the evolutionary robotics (ER) approach for designing a robot controller that consists of a recurrent neural network. The controllers are evaluated in the collective step-climbing task conducted by computer simulations. The results show that the ER approach successfully designed the robot gait to achieve the task. Additionally, the results of the analysis confirm that the robot obtained the actions to support other robots along with climbing other robots.
• Learning from the Past: Regularization by Validation.

  Enzhi Zhang, Mohamed Wahib, Masaharu Munetomo

  SCIS/ISIS 1 - 8 2022
• Many-Constraint and Many-Objective optimization with Bias Index for Intercloud Multi-Workflow Resource Provisioning.

  Courtney Powell, Katsunori Miura, Masaharu Munetomo

  SCIS/ISIS 1 - 8 2022/11/29
• Accelerating the Evolutionary Algorithms by Gaussian Process Regression with ε-greedy acquisition function.

  Rui Zhong, Enzhi Zhang, Masaharu Munetomo

  CoRR abs/2210.06814 2022
• Accelerating the Genetic Algorithm for Large-scale Traveling Salesman Problems by Cooperative Coevolutionary Pointer Network with Reinforcement Learning.

  Rui Zhong, Enzhi Zhang, Masaharu Munetomo

  CoRR abs/2209.13077 2022
• Cooperative coevolutionary Modified Differential Evolution with Distance-based Selection for Large-Scale Optimization Problems in noisy environments through an automatic Random Grouping.

  Rui Zhong, Masaharu Munetomo

  CoRR abs/2209.00777 2022
• Accelerating differential evolution algorithm with Gaussian sampling based on estimating the convergence points.

  Rui Zhong, Masaharu Munetomo

  CoRR abs/2208.14619 2022
• Cooperative coevolutionary hybrid NSGA-II with Linkage Measurement Minimization for Large-scale Multi-objective optimization.

  Rui Zhong, Masaharu Munetomo

  CoRR abs/2208.13415 2022
• Optimal answer generation by equivalent transformation incorporating multi-objective genetic algorithm.

  Katsunori Miura, Courtney Powell, Masaharu Munetomo

  Soft Computing 26 (19) 10535 - 10546 2022
• Evolving collective step-climbing behavior in multi-legged robotic swarm.

  Daichi Morimoto, Motoaki Hiraga, Naoya Shiozaki, Kazuhiro Ohkura, Masaharu Munetomo

  Artif. Life Robotics 27 (2) 333 - 340 2022
• Distribution system for japanese synthetic population data with protection level

  Tadahiko Murata, Susumu Date, Yusuke Goto, Toshihiro Hanawa, Takuya Harada, Manabu Ichikawa, Hao Lee, Masaharu Munetomo, Akiyoshi Sugiki

  Proceedings - International Conference on Machine Learning and Cybernetics 2020-December 187 - 193 2160-133X 2020/12/02 

  In this paper, we introduce a distribution system of synthesized data of Japanese population using Interdisciplinary Large-scale Information Infra-structures in Japan. Synthetic population is synthesized based on the statistics of the census that are conducted by the government and publicly released. Therefore, the synthesized data have no privacy data. However, it is easy to estimate the compositions of households, working status in a certain area from the synthetic population. Therefore, we currently distribute the synthesized data only for public or academic purposes. For academic purposes, it is important to encourage scholars or researchers to use a large-scale data of households, we define protection levels for the attributes in the synthetic populations. According to the protection levels, we distribute the data with proper attributes to those who try to use them. We encourage researchers to use the synthetic populations to be familiar to large-scale data processing.
• GTOPX Space Mission Benchmarks.

  Martin Schlueter, Mehdi Neshat, Mohamed Wahib, Masaharu Munetomo, Markus Wagner 0007

  CoRR abs/2010.07517 2020
• Distribution of Synthetic Populations of Japan for Social Scientists and Social Simulation Researchers.

  Tadahiko Murata, Takuya Harada, Manabu Ichika Wa, Yusuke Goto, Lee Hao, Susumu Date, Masaharu Munetomo, Akiyoshi Sugiki

  1 - 5 2019 [Refereed][Not invited]
  
• Constrained Multi-objective Optimization Method for Practical Scientific Workflow Resource Selection.

  Courtney Powell, Katsunori Miura, Masaharu Munetomo

  Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings Springer 683 - 694 2019 [Refereed][Not invited]
  
• Network Structural Vulnerability: A Multiobjective Attacker Perspective.

  Luca Faramondi, Gabriele Oliva, Stefano Panzieri, Federica Pascucci, Martin Schlueter, Masaharu Munetomo, Roberto Setola

  IEEE Trans. Syst. Man Cybern. Syst. 49 (10) 2036 - 2049 2019 [Refereed][Not invited]
  
• A Mixed-Integer Extension for ESA's Cassini1 Space Mission Benchmark.

  Martin Schlueter, Masaharu Munetomo

  IEEE Congress on Evolutionary Computation, CEC 2019, Wellington, New Zealand, June 10-13, 2019 912 - 919 2019 [Refereed][Not invited]
  
• Massively parallelized co-evaluation for many-objective space trajectory optimization.

  Martin Schlueter, Masaharu Munetomo

  Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 ACM 306 - 307 2018 [Refereed][Not invited]
  
• Towards a small diverse pareto-optimal solutions set generator for multiobjective optimization problems.

  Courtney Powell, Katsunori Miura, Masaharu Munetomo

  Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 ACM 298 - 299 2018 [Refereed][Not invited]
  
• Introducing a linkage identification considering non-monotonicity to multi-objective evolutionary optimization with decomposition for real-valued functions.

  Kousuke Izumiya, Masaharu Munetomo

  Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 ACM 179 - 180 2018 [Refereed][Not invited]
  
• A surrogate-assisted selection scheme for genetic algorithms employing multi-layer neural networks.

  Masaki Fujiwara, Masaharu Munetomo

  Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 ACM 41 - 42 2018 [Refereed][Not invited]
  
• Optimal Cloud Resource Selection Method Considering Hard and Soft Constraints and Multiple Conflicting Objectives.

  Courtney Powell, Katsunori Miura, Masaharu Munetomo

  11th IEEE International Conference on Cloud Computing, CLOUD 2018, San Francisco, CA, USA, July 2-7, 2018 IEEE Computer Society 831 - 835 2018 [Refereed][Not invited]
  
• Optimal and Feasible Cloud Resource Configurations Generation Method for Genomic Analytics Applications.

  Katsunori Miura, Courtney Powell, Masaharu Munetomo

  2018 IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2018, Nicosia, Cyprus, December 10-13, 2018 IEEE Computer Society 137 - 144 2018 [Refereed][Not invited]
  
• A Level-Wise Load Balanced Scientific Workflow Execution Optimization Using NSGA-II

  Phyo Thandar Thant, Courtney Powell, Martin Schlueter, Masaharu Munetomo

  Proceedings - 2017 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2017 882 - 889 2017/07/10 [Refereed][Not invited]
   

  Over the past decade, cloud computing has grown in popularity for the processing of scientific applications as a result of the scalability of the cloud and the ready availability of on-demand computing and storage resources. It is also a cost-effective alternative for scientific workflow executions with a pay-per-use paradigm. However, providing services with optimal performance at the lowest financial resource deployment cost is still challenging. Several fine-grained tasks are included in scientific workflow applications, and efficient execution of these tasks according to their processing dependency to minimize the overall makespan during workflow execution is an important research area. In this paper, a system for level-wise workflow makespan optimization and virtual machine deployment cost minimization for overall workflow optimization in cloud infrastructure is proposed. Further, balanced task clustering, to ensure load balancing in different virtual machine instances at each workflow level during workflow execution, is also considered. The system retrieves the necessary workflow information from a directed acyclic graph and uses the non-dominated sorting genetic algorithm II (NSGA-II) to carry out multiobjective optimization. Pareto front solutions obtained for makespan time and instance resource deployment cost for several scientific workflow applications verify the efficacy of our system.
• Multi-objective Evolutionary optimization based on Decomposition with Linkage Identification considering monotonicity

  Kousuke Izumiya, Masaharu Munetomo

  2017 IEEE Congress on Evolutionary Computation, CEC 2017 - Proceedings 905 - 912 2017/07/05 [Refereed][Not invited]
   

  We propose a Decomposition-based Multi-objective Evolutionary Algorithm (MOEA/D) that incorporates a linkage identification technique to enhance the ability to solve difficult multi-objective optimization problems that have complex interactions among genes. Ensuring tight linkages is essential for genetic recombination operators to work effectively by preserving building blocks. For problems which are difficult to ensure tight linkages in encoding, the dependencies among loci have to be analyzed to identify the linkages for each building block. The proposed MOEA/D employs Linkage Identification with non-Monotonicity Detection (LIMD) to identify the linkages among pairs of loci by checking the non-monotonicity of fitness differences caused by pairwise perturbations for each scalar function in the MOEA/D. The results of numerical experiments conducted using a difficult multi-objective test function in which each building block is loosely encoded over the strings indicate that the proposed MOEA/D-LIMD outperforms the original MOEA/D and MOEA/D with tree-based graphical model (MOEA/D-GM).
• MIDACO Parallelization Scalability on 200 MINLP Benchmarks

  Martin Schlueter, Masaharu Munetomo

  Journal of Artificial Intelligence and Soft Computing Research 7 (3) 171 - 181 2449-6499 2017/07/01 [Refereed][Not invited]
   

  This contribution presents a numerical evaluation of the impact of parallelization on the performance of an evolutionary algorithm for mixed-integer nonlinear programming (MINLP). On a set of 200 MINLP benchmarks the performance of the MIDACO solver is assessed with gradually increasing parallelization factor from one to three hundred. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to CPU-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.
• Multiobjective Level-Wise Scientific Workflow Optimization in IaaS Public Cloud Environment

  Phyo Thandar Thant, Courtney Powell, Martin Schlueter, Masaharu Munetomo

  SCIENTIFIC PROGRAMMING 1058-9244 2017 [Refereed][Not invited]
   

  Cloud computing in the field of scientific applications such as scientific big data processing and big data analytics has become popular because of its service oriented model that provides a pool of abstracted, virtualized, dynamically scalable computing resources and services on demand over the Internet. However, resource selection to make the right choice of instances for a certain application of interest is a challenging problem for researchers. In addition, providing services with optimal performance at the lowest financial resource deployment cost based on users' resource selection is quite challenging for cloud service providers. Consequently, it is necessary to develop an optimization system that can provide benefits to both users and service providers. In this paper, we conduct scientific workflow optimization on three perspectives: makespan minimization, virtual machine deployment cost minimization, and virtual machine failure minimization in the cloud infrastructure in a level-wise manner. Further, balanced task assignment to the virtual machine instances at each level of the workflow is also considered. Finally, system efficiency verification is conducted through evaluation of the results with different multiobjective optimization algorithms such as SPEA2 and NSGA-II.
• Numerical Optimization of ESA's Messenger Space Mission Benchmark

  Martin Schlueter, Mohamed Wahib, Masaharu Munetomo

  APPLICATIONS OF EVOLUTIONARY COMPUTATION, EVOAPPLICATIONS 2017, PT I 10199 725 - 737 0302-9743 2017 [Refereed][Not invited]
   

  The design and optimization of interplanetary space mission trajectories is known to be a difficult challenge. The trajectory of the Messenger mission (launched by NASA in 2004) is one of the most complex ones ever created. The European Space Agency (ESA) makes available a numerical optimization benchmark which resembles an accurate model of Messengers full mission trajectory. This contribution presents an optimization approach which is capable to (robustly) solve ESA's Messenger full mission benchmark to its putative global solution within 24 h run time on a moderate sized computer cluster. The considered algorithm, named MXHPC, is a parallelization framework for the MIDACO optimization algorithm which is an evolutionary method particularly suited for space trajectory design. The presented results demonstrate the effectiveness of evolutionary computing for complex real-world problems which have been previously considered intractable.
• Multi-Objective Hadoop Configuration Optimization using Steady-State NSGA-II

  Phyo Thandar Thant, Courtney Powell, Akiyoshi Sugiki, Masaharu Munetomo

  2016 JOINT 8TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS (SCIS) AND 17TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS (ISIS) 293 - 298 2016 [Refereed][Not invited]
   

  Hadoop configuration optimization is very challenging because of the complexity of its framework. And optimized Hadoop parameter configuration settings depend significantly on the performance of MapReduce applications in the cluster. Although much research has been conducted on Hadoop parameters configuration optimization, configuring its resource setting parameters to minimize the execution time of MapReduce jobs in clusters still needs a lot of continuing researches. Further, determining the type of machine instances that should be used to minimize the resource usage cost for executing applications in clusters is also difficult. This paper addresses these problems by optimizing the instance resource usage and execution time of MapReduce tasks using a multi-objective steady-state Non-dominated Sorting Genetic Algorithm II (ssNSGA-II) approach. In this approach, the instance resource usage cost of MapReduce tasks is calculated based on the cost of machine instance types and the number of machine instances in the Hadoop cluster. The optimized configuration is identified by selecting an optimal setting that satisfies two objective functions associated with instance resource usage and execution time minimization, from Pareto optimal front solutions. Although dynamic machine instance type is considered within the search process in our system, dynamic cluster size is out of consideration and intended to be carried out in our future. Experiments conducting using workloads from the HiBench benchmark on a high specification 6-node Hadoop cluster verify the efficacy of our proposed approach.
• Evaluation of Three Steady-State NSGA-III Offspring Selection Schemes for Many-Objective Optimization

  Courtney Powell, Masaharu Munetomo, Phyo Thandar Thant

  2016 JOINT 8TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS (SCIS) AND 17TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS (ISIS) 166 - 171 2016 [Refereed][Not invited]
   

  In this study, we implemented three steady-state versions of NSGA-III that differ by the manner in which the offspring combined with the parent population is selected. These three schemes were then evaluated on the standard problem sets DTLZ1-4 in terms of four popular criteria: inverse generational distance (IGD), hypervolume (HV), convergence, and diversity. The results obtained suggest that utilizing a selection scheme in which the offspring is selected from the first non-dominated rank results in better solutions than other steady-state offspring selection schemes.
• Intercloud Brokerages based on PLS Method for deploying Infrastructures for Big Data Analytics

  Katsunori Miura, Tazro Ohta, Courtney Powell, Masaharu Munetomo

  2016 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA) 2097 - 2102 2016 [Refereed][Not invited]
   

  This paper proposes an intercloud brokerage method for system infrastructure deployments of genomic big data analytics workflows. The proposed method utilizes a conjunction of universally quantified atomic formula to describe requirements given by users, and selects combinations of cloud services based on logical reasoning by the replacement of definite clause sets created from conjunction of the atomic formulas, while preserving the declarative meaning of the system infrastructures' constraint conditions. We also define algorithms for the replacement of definite clause sets, and present an example of the use of the proposed intercloud brokerage method.
• A Predicate Logic-defined Specification Method for Systems Deployed by Intercloud Brokerages

  Katsunori Miura, Masaharu Munetomo

  2016 IEEE INTERNATIONAL CONFERENCE ON CLOUD ENGINEERING WORKSHOP (IC2EW) 172 - 177 2016 [Refereed][Not invited]
   

  This paper proposes a formal predicate logic-based method for the specification of intercloud information systems comprising combinations of cloud services. The proposed framework utilizes predicates with variables in universally quantified atoms to provide general descriptive capability for a wide variety of cloud services and their various properties. We define the proposed Predicate Logic-defined Specification (PLS) method and explain how it can be applied to describe three-tier web applications using an example global-scale intercloud environment. We also discuss the effectiveness of the proposed method in Cloud Service Brokerage (CSB) scenarios compared with conventional approaches based on Satisfiability problems (SAT) and Satisfiability Modulo Theories (SMT).
• Development of a Multi-player Interactive Genetic Algorithm-based 3D Modeling System for Glasses

  Takahito Seyama, Masaharu Munetomo

  2016 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 846 - 852 2016 [Refereed][Not invited]
   

  This paper proposes a 3D modeling system that uses multi-player interactive genetic algorithm (MiGA) to simplify the 3D modeling process for ordinary persons who wish to model pairs of glasses. The proposed system has three advantages: First, users are able to create 3D models via simple operations such as evaluation of 3D models. Second, this system reduces user fatigue by showing the information searched for and utilized by similar users, discovered by collaborative filtering. Third, this system also facilitates collaboration among a large number of users by employing Platform as-a Service (PaaS) and NoSQL database for scalability. The results of real and pseudo user experiments conducted verify the efficacy of the proposed system.
• Numerical Assessment of the Parallelization Scalability on 200 MINLP Benchmarks

  Martin Schlueter, Masaharu Munetomo

  2016 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 830 - 837 2016 [Refereed][Not invited]
   

  This contribution addresses the question if and how the impact of parallelization can influence the performance of an evolutionary algorithm on constrained mixed-integer nonlinear optimization problems. On a set of 200 MINLP benchmarks the performance of the MIDACO solver is numerically assessed with gradually increasing parallelization factor from 1 to 100. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to cpu-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.
• Screening for FtsZ Dimerization Inhibitors Using Fluorescence Cross-Correlation Spectroscopy and Surface Resonance Plasmon Analysis

  Shintaro Mikuni, Kota Kodama, Akira Sasaki, Naoki Kohira, Hideki Maki, Masaharu Munetomo, Katsumi Maenaka, Masataka Kinjo

  PLOS ONE 10 (7) e0130933  1932-6203 2015/07 [Refereed][Not invited]
   

  FtsZ is an attractive target for antibiotic research because it is an essential bacterial cell division protein that polymerizes in a GTP-dependent manner. To find the seed chemical structure, we established a high-throughput, quantitative screening method combining fluorescence cross-correlation spectroscopy (FCCS) and surface plasmon resonance (SPR). As a new concept for the application of FCCS to polymerization-prone protein, Staphylococcus aureus FtsZ was fragmented into the N-terminal and C-terminal, which were fused with GFP and mCherry (red fluorescent protein), respectively. By this fragmentation, the GTP-dependent head-to-tail dimerization of each fluorescent labeled fragment of FtsZ could be observed, and the inhibitory processes of chemicals could be monitored by FCCS. In the first round of screening by FCCS, 28 candidates were quantitatively and statistically selected from 495 chemicals determined by in silico screening. Subsequently, in the second round of screening by FCCS, 71 candidates were also chosen from 888 chemicals selected via an in silico structural similarity search of the chemicals screened in the first round of screening. Moreover, the dissociation constants between the highest inhibitory chemicals and Staphylococcus aureus FtsZ were determined by SPR. Finally, by measuring the minimum inhibitory concentration, it was confirmed that the screened chemical had antibacterial activity against Staphylococcus aureus, including methicillin-resistant Staphylococcus aureus (MRSA).
• Distributed Denial of Services Attack Protection System with Genetic Algorithms on Hadoop Cluster Computing Framework

  Masataka Mizukoshi, Masaharu Munetomo

  2015 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 1575 - 1580 2015 [Refereed][Not invited]
   

  DDoS attacks become serious as one of the menaces of the Internet security. It is difficult to prevent because DDoS attacker send spoofing packets to victim which makes the identification of the origin of attacks very difficult. A series of techniques have been studied such as pattern matching by learning the attack pattern and abnormal traffic detection. However, pattern matching approach is not reliable because attackers always set attacks of different traffic patterns and pattern matching approach only learns from the past DDoS data. Therefore, a reliable system has to watch what kind of attacks are carried out now and investigate how to prevent those attacks. Moreover, the amount of traffic flowing through the Internet increase rapidly and thus packet analysis should be done within considerable amount of time. This paper proposes a scalable, real-time traffic pattern analysis based on genetic algorithm to detect and prevent DDoS attacks on Hadoop distributed processing infrastructure. Experimental results demonstrate the effectiveness of our scalable DDoS protection system.
• アカデミッククラウド実現にむけたクラウド支援サービス (インターネットアーキテクチャ)

  合田 憲人, 山地 一禎, 中村 素典, 横山 重俊, 吉岡 信和, 政谷 好伸, 西村 浩二, 棟朝 雅晴

  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 一般社団法人電子情報通信学会 114 (236) 1 - 5 0913-5685 2014/10/07 [Not refereed][Not invited]
  
• Human-based Genetic Algorithm for Facilitating Practical Use of Data in the Internet

  Ryosuke Hasebe, Rina Kouda, Kei Ohnishi, Masaharu Munetomo

  2014 JOINT 7TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS (SCIS) AND 15TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS (ISIS) 1327 - 1332 2014 [Not refereed][Not invited]
   

  A variety of data are accumulated in the Internet and the data are increasing in amount everyday, for example, open data provided by governments of multiple countries. Utilizing such data might be linked to creating new businesses or services. Therefore, it would be useful if we have a system that helps users discuss purposes to utilize the data quickly and efficiently. So, we conceptually present a system implementing a human-based genetic algorithm that is intended to help users discuss purposes to utilize the data quickly and efficiently, and then develop a web-based system for discussing suitable tags for given images according to the concept. We also conduct subjective tests for evaluating the developed system. The results do not show statistical significant difference between the developed system and a conventional way, but we obtain several positive comments about the usability of the developed system.
• Design of an SSO Authentication Infrastructure for Heterogeneous Inter-cloud Environments

  Courtney Powell, Takashi Aizawa, Masaharu Munetomo

  2014 IEEE 3RD INTERNATIONAL CONFERENCE ON CLOUD NETWORKING (CLOUDNET) 102 - 107 2374-3239 2014 [Refereed][Not invited]
   

  This paper outlines the design of an authentication infrastructure for linking distributed heterogeneous cloud systems managed by different cloud management middleware to enable them to interoperate as an integrated inter-cloud system. This authentication infrastructure achieves single sign-on (SSO), which allows users to log in once and access the various cloud systems without being asked to log in again at each system. Further, it does so without changing the design of the existing cloud systems by using a proxy certificate repository and Shibboleth authentication technology. We also report on a prototype implementation of the system that validates the design of the authentication infrastructure.
• Parallelization for Space Trajectory Optimization

  Martin Schlueter, Masaharu Munetomo

  2014 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 832 - 839 2014 [Refereed][Not invited]
   

  The impact of parallelization on the optimization process of space mission trajectories is investigated in this contribution. As space mission trajectory reference model, the well known Cassini1 benchmark, published by the European Space Agency (ESA), is considered and solved here with the MIDACO optimization software. It can be shown that significant speed ups can be gained by applying parallelization.
• An adaptive parameter binary-real coded genetic algorithm for constraint optimization problems: Performance analysis and estimation of optimal control parameters

  Omar Arif Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama

  INFORMATION SCIENCES 233 54 - 86 0020-0255 2013/06 [Refereed][Not invited]
   

  Real parameter constrained problems are an important class of optimization problems that are encountered frequently in a variety of real world problems. On one hand, Genetic Algorithms (GAs) are an efficient search metaheuristic and a prominent member within the family of Evolutionary Algorithms (EAs), which have been applied successfully to global optimization problems. However, genetic operators in their standard forms are blind to the presence of constraints. Thus, the extension of GAs to constrained optimization problems by incorporating suitable handing techniques is an active direction within GAs research. Recently, we have proposed a Binary Real coded Genetic Algorithm (BRGA). BRGA is a new hybrid approach that combines cooperative Binary coded GA (BGA) with Real coded GA (RGA). It employs an adaptive parameter-based hybrid scheme that distributes the computational power and regulates the interactions between the cooperative versions, which operate in a sequential time-interleaving manner. In this study, we aim to extend BRGA to constrained problems by introducing a modified dynamic penalty function into the architecture of BRGA. We use the CEC'2010 benchmark suite of 18 functions to analyze the quality, time and scalability performance of BRGA. To investigate the effectiveness of the proposed modification, we compare the performance of BRGA under both the original and the modified penalty functions. Moreover, to demonstrate the performance of BRGA, we compare it with the performance of some other EAs from the literature. We also implement a robust parameter tuning procedure that relies on techniques from statistical testing, experimental design and Response Surface Methodology (RSM) to estimate the optimal values for the control parameters to secure a good performance by BRGA against specific problems at hand. (c) 2013 Elsevier Inc. All rights reserved.
• Parallelization strategies for evolutionary algorithms for MINLP

  Martin Schlueter, Masaharu Munetomo

  2013 IEEE Congress on Evolutionary Computation, CEC 2013 635 - 641 2013 [Refereed][Not invited]
   

  Two different parallelization strategies for evolutionary algorithms for mixed integer nonlinear programming (MINLP) are discussed and numerically compared in this contribution. The first strategy is to parallelize some internal parts of the evolutionary algorithm. The second strategy is to parallelize the MINLP function calls outside and independently of the evolutionary algorithm. The first strategy is represented here by a genetic algorithm (arGA) for numerical testing. The second strategy is represented by an ant colony optimization algorithm (MIDACO) for numerical testing. It can be shown that the first parallelization strategy represented by arGA is inferior to the serial version of MIDACO, even though if massive parallelization via GPGPU is used. In contrast to this, theoretical and practial tests demonstrate that the parallelization strategy of MIDACO is promising for cpu-time expensive MINLP problems, which often arise in real world applications. © 2013 IEEE.
• Towards thought control of next-generation wearable computing devices

  Courtney Powell, Masaharu Munetomo, Martin Schlueter, Masataka Mizukoshi

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8211 427 - 438 0302-9743 2013 [Refereed][Not invited]
   

  A new wearable computing era featuring devices such as Google Glass, smartwatches, and digital contact lenses is almost upon us, bringing with it usability issues that conventional human computer interaction (HCI) modalities cannot resolve. Brain computer interface (BCI) technology is also rapidly advancing and is now at a point where noninvasive BCIs are being used in games and in healthcare. Thought control of wearable devices is an intriguing vision and would facilitate more intuitive HCI however, to achieve even a modicum of control BCI currently requires massive processing power that is not available on mobile devices. Cloud computing is a maturing paradigm in which elastic computing power is provided on demand over networks. In this paper, we review the three technologies and take a look at possible ways cloud computing can be harnessed to provide the computational power needed to facilitate practical thought control of next-generation wearable computing devices. © Springer International Publishing 2013.
• A scalable infrastructure of interactive evolutionary computation to evolve services online with data

  Masaharu Munetomo, Shintaro Bando

  Proceedings - 2013 IEEE International Conference on Big Data, Big Data 2013 28  2013 [Refereed][Not invited]
   

  This paper proposes a scalable framework to process and evolve services online adaptively from big data obtained from their users employing interactive evolutionary computation realized on a scalable infrastructure as platform as a service. Instead of collecting/storing/processing/analyzing big data to improve services offline, the proposed framework enables us to evolve and optimize adaptively every when collecting data from users interactively. © 2013 IEEE.
• arGA: Adaptive resolution micro-genetic algorithm with tabu search to solve MINLP problems using GPU

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  Natural Computing Series 46 83 - 104 1619-7127 2013 [Refereed][Not invited]
   

  In this chapter,we propose a newapproach to solve the most general form of global optimization problems, namely, non-convex Mixed-Integer Nonlinear Programming (MINLP) and non-convex Nonlinear Programming (NLP) problems. The target is to solve MINLP/NLP problems from different domains of research in fewer fitness evaluations as compared to other state-of-the-art stochastic algorithms in the area. The algorithm is GPU compatible and shows remarkable speedups over nVidia’s CUDA-compatible GPUs. MINLP problems involve both discrete and continuous variables with several active nonlinear equality and inequality constraints making them extremely difficult to solve. The proposed algorithm is named the adaptive resolution Genetic Algorithm (arGA) as it exploits the concept of controlling the search space size and resolution in an adaptive manner. Using entropy measures, the proposed algorithm adaptively controls the intensity of the genetic search in a given sub-solution space, i.e., promising regions are searched more intensively as compared to other regions. The algorithm is equipped with an asynchronous adaptive local search operator to further improve the performance. Niching is incorporated by using a technique inspired from the Tabu search. The algorithm reduces the chances of convergence to local optima by maintaining a list of already visited optima and penalizing their neighborhoods. The proposed technique was able to find the best-known solutions to extremely difficult MINLP/NLP problems in fewer fitness evaluations and in a competitive amount of time. The results section discusses the performance of the algorithm and the effect of different operators by using a variety ofMINLP/NLPs from different problem domains. GPU implementation shows a speedup of up to 42× for single precision and 20× for double precision implementation over the nVidia C2050 GPU architecture.
• Constructing a robust services-oriented inter-cloud portal based on an autonomic model and FOSS

  Courtney Powell, Masaharu Munetomo, Attia Wahib, Takashi Aizawa

  Proceedings - 2013 IEEE/ACM 6th International Conference on Utility and Cloud Computing, UCC 2013 458 - 463 2013 [Refereed][Not invited]
   

  The aim of the simple heterogeneous inter-cloud manager (SHINCLOM) project is to develop a prototype web-based single sign-on inter-cloud management portal that gives users the ability to easily configure and launch inter-cloud VPCs, HPC clusters, and autonomic applications and services. We employ a model-based approach in which the various requirements of the project are mapped to the layers of a proposed autonomic model and implemented using free open source software (FOSS). In this paper, we outline the requirements of the project, discuss our overall construction methodology, and give an overview of the sections implemented to date. © 2013 IEEE.
• Design of Authentication System for High Performance Distributed Computing Environment

  Kento Aida, Manabu Higashida, Eisaku Sakane, Hirofumi Amano, Katsushi Kobayashi, Masaharu Munetomo, Ryusuke Egawa, Osamu Tatebe, Yoshikazu Kamoshida, Shin'ichiro Takizawa, Toru Nagai, Takeshi Iwashita, Yutaka Ishikawa

  先進的計算基盤システムシンポジウム論文集 一般社団法人情報処理学会 5 (2012) 227 - 236 0387-5806 2012/05/09 [Not refereed][Not invited]
   

  This paper presents design of the authentication system for the High Performance Computing Infrastructure (HPCI), which is currently deployed by the Ministry of Education, Culture, Sports, Science and Technology. The presented authentication system enables single sign-on to computers and shared storages on HPCI by utilizing the authentication mechanism on the Grid, "Grid Security Infrastructure (GSI)", and the identity federation mechanism, "Shibboleth". This paper also presents the experiments conducted on the testbed for the presented authentication system.
• A GPU Accelerated Fragment-based De Novo Ligand Design by a Bayesian Optimization Algorithm (Bioinformatics Vol.5)

  Wahib Mohamed, Munawar Asim, Munetomo Masaharu

  情報処理学会論文誌 論文誌トランザクション 情報処理学会 2011 (2) 7 - 17 1882-7772 2012/04 [Not refereed][Not invited]
  
• How to Apply Evolutionary Computation

  MUNETOMO Masaharu, SOMEYA Hiroshi

  The Journal of The Institute of Electrical Engineers of Japan 一般社団法人 電気学会 132 (4) 204 - 207 1340-5551 2012/04/01 [Not refereed][Not invited]
   

  This article has no abstract.
• -

  Hiroki Kashiwazaki, Masaharu Munetomo, Yoshiaki Takai

  Proceedings of NORTH Internet Symposium 2012 18 101 - 108 2012/02 [Refereed][Not invited]
  
• Toward A Genetic Algorithm Based Flexible Approach for the Management of Virtualized Application Environments in Cloud Platforms

  Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama

  2012 21ST INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS (ICCCN) 1 - 9 1095-2055 2012 [Refereed][Not invited]
   

  Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological impact. On the other hand, virtualization adds a greater flexibility to the resource managers in addressing such challenges. However, at the same time, it imposes a further challenge of added management complexity. Recently, we have proposed a resource management model for cloud platforms, which utilizes a new resource mapping formulation and relays on a hybrid virtualization framework in an attempt to realize a resource manager that intelligently adapts the available cloud resources to satisfy the conflicting objectives of the running applications and underlying infrastructures' requirements. Moreover, we have proposed state of the art Binary-Real coded Genetic Algorithm (BRGA), which has been applied successfully to a wide spectrum of global and constrained optimization problems from the known benchmark suites. In this paper, we aim to proceed by proposing a mathematical model and a modified version of BRGA to validate our model. In addition, we aim to evaluate the feasibility, effectiveness and scalability of our approach through simulation experiments.
• Estimation of Distribution Algorithm with Mixture of Bayesian Networks

  Hori Shinya, Munetomo Masaharu, Akama Kiyoshi

  Transaction of the Japanese Society for Evolutionary Computation 進化計算学会 3 (2) 63 - 72 2012 [Refereed][Not invited]
   

  This paper proposes a new method of Estimation Distribution Algorithm (EDA) named Bayesian Optimization Algorithm with Mixture Distribution (BOA-MD) that employs mixture of multiple Bayesian Networks to solve complex problems. In order to solve complex problems that are modeled by multiple Bayesian networks with hidden variables, the original BOA needs a large computation cost to model multiple probabilistic structures as a large, complex Bayesian network.The BOA-MD tries to build multiple models of Bayesian networks considering hidden variables with Expectation Maximization (EM) method to express all the structures of probabilistic distribution.The mixture of Bayesian networks is composed of a hidden variable C and some Bayesian Networks. Each composed Bayesian network can express each problem structure of multiple distributions. We perform numerical experiments by two test functions: Cross-Trap function and Triple-Trap function. These two test functions are to represent problems with multiple distributions. BOA-MD can solve these test problems with smaller number of fitness evaluations and larger modeling overheads than those by BOA for Cross-Trap5 function. This is because BOA-MD needs large computation time to construct Mixture of Bayesian Network. The BOA-MD can solve the problem faster than the original BOA when the overhands of each fitness evaluation becomes larger. At Triple-Trap function, BOA-MD can detect better solution than BOA.
• Toward A Genetic Algorithm Based Flexible Approach for the Management of Virtualized Application Environments in Cloud Platforms

  Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama

  2012 21ST INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS (ICCCN) 1095-2055 2012 [Refereed][Not invited]
   

  Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological impact. On the other hand, virtualization adds a greater flexibility to the resource managers in addressing such challenges. However, at the same time, it imposes a further challenge of added management complexity. Recently, we have proposed a resource management model for cloud platforms, which utilizes a new resource mapping formulation and relays on a hybrid virtualization framework in an attempt to realize a resource manager that intelligently adapts the available cloud resources to satisfy the conflicting objectives of the running applications and underlying infrastructures' requirements. Moreover, we have proposed state of the art Binary-Real coded Genetic Algorithm (BRGA), which has been applied successfully to a wide spectrum of global and constrained optimization problems from the known benchmark suites. In this paper, we aim to proceed by proposing a mathematical model and a modified version of BRGA to validate our model. In addition, we aim to evaluate the feasibility, effectiveness and scalability of our approach through simulation experiments.
• How to Apply Evolutionary Computation

  MUNETOMO MASAHARU, SOMEYA HIROSHI

  電気学会誌 132 (4) 204 - 207 1340-5551 2012 [Not refereed][Not invited]
  
• A GPU accelerated fragment-based de novo ligand design by a bayesian optimization algorithm

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  IPSJ Transactions on Bioinformatics 5 7 - 17 1882-6679 2012 [Refereed][Not invited]
   

  De Novo ligand design is an automatic fragment-based design of molecules within a protein binding site of a known structure. A Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, is introduced to join predocked fragments with a user-supplied list of fragments. A novel feature proposed is the simultaneous optimization of force field energy and a term enforcing 3D-overlap to known binding mode(s). The performance of the algorithm is tested on Liver X receptors (LXRs) using a library of about 14,000 fragments and the binding mode of a known heterocyclic phenyl acetic acid to bias the design. We further introduce the use of GPU (Graphics Processing Unit) to overcome the excessive time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragment sets and target receptors for more complex instances. The results show how the nVidia's Tesla C2050 GPU was utilized to enable the generation of complex agonists effectively. In fact, eight of the 1,809 molecules designed for LXRs are found in the ZINC database of commercially available compounds.
• 410 Study of a light-received system with configuration of a plant shoot

  Nakai Shingo, Obara Shinya, Tanaka Eiichi, Konno Daisuke, Munetomo Masaharu

  The Proceedings of the Symposium on Environmental Engineering 一般社団法人 日本機械学会 2012 (0) 277 - 278 2012 [Not refereed][Not invited]
   

  It is thought that plants have evolved to modulate the amount of light received by the leaves in order to competition for survival. Investigation of a plant shoot configuration is used to obtain valuable information concerning the received light system. As an example, it is thought that the leaves of various shape has a role important about die received light characteristics of the plant individual. In this research, we performed a numerical experiment that simulates the plant shoot by using a genetic algorithm analysis program in order to investigate the received light characteristics of a plant shoot. As a result, the relation between the placement of plant shoot of various shapes and the light-receiving amount is clarified.
• Development of a Plant Configuration Photoreceptor Optimized for the Objective of Maximizing Light-Received Quantity

  Eiichi Tanaka, Shin'ya Obara, Shingo Nakai, Daisuke Konno, Masaharu Munetomo

  2012 15TH INTERNATIONAL CONFERENCE ON ELECTRICAL MACHINES AND SYSTEMS (ICEMS 2012) 2012 [Not refereed][Not invited]
   

  Investigation of a whole plant configuration is used to obtain valuable information concerning the received light system. As an example, it is thought that branching of a plant has an important role about light receiving properties of the individual. In this research, development of the analysis program by simulating branch of a plant using L-system was tried, because numerical value experiments on light receiving properties of the plant. From these results, the relations of the analysis program applied to investigate branching of the plant shoot and the light received quantity was developed.
• 北海道大学アカデミッククラウドにおけるコンテンツマネジメントシステムの展開

  棟朝雅晴, 高井昌彰

  情報科学技術フォーラム FIT 2011 15-18  2011/08/22 [Not refereed][Not invited]
  
• A framework for cloud embedded Web services utilized by cloud applications

  Mohamed Wahi, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  Proceedings - 2011 IEEE World Congress on Services, SERVICES 2011 265 - 271 2011 [Refereed][Not invited]
   

  Cloud computing is impacting the modern Internet computing and businesses in every aspect. One feature of clouds is the convenience of using the services offered by the cloud. Consequently, most cloud service providers use WS for users and developers to interface with the cloud. However, the current cloud WS are focused into core and fundamental modern computing functionalities. We anticipate as cloud developments tools mature and cloud applications become more popular, there will be an opportunity for designing and implementing applications/services to be embedded in the cloud for use by applications in the cloud. We propose a framework for WS deployment in the cloud to be usable by applications residing in the same cloud. The framework capitalizes on the cloud strong points to offer a higher value to the service consumer inside the cloud. The authoritative nature of clouds would enable more efficient models for WS publishing, indexing and description. Moreover, being hosted in the cloud, WS can build on the high scalability offered by the cloud with a much higher reliability. Finally, scheduling the instances using the WS in bundle with the WS instances could offer a LAN-like connectivity performance driving down the latency to the magnitude of lower microseconds. In this paper, we highlight the challenges and opportunities of cloud applications using cloud embedded Web services. We give a description of the different aspects by illustrating the different components, together with an end-to-end use case to show the applicability of the proposed system. © 2011 IEEE.
• Solving extremely difficult MINLP problems using adaptive resolution Micro-GA with Tabu search

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6683 203 - 217 0302-9743 2011 [Refereed][Not invited]
   

  Non convex mixed integer non-linear programming problems (MINLPs) are the most general form of global optimization problems. Such problems involve both discrete and continuous variables with several active non-linear equality and inequality constraints. In this paper, a new approach for solving MINLPs is presented using adaptive resolution based micro genetic algorithms with local search. Niching is incorporated in the algorithm by using a technique inspired from the tabu search algorithm. The proposed algorithm adaptively controls the intensity of the genetic search in a given sub-solution space, i.e. promising regions are searched more intensely as compared to other regions. The algorithm reduces the chances of convergence to a local minimum by maintaining a list of already visited minima and penalizing their neighborhoods. This technique is inspired from the tabu list strategy used in the tabu search algorithm. The proposed technique was able to find the best-known solutions to extremely difficult MINLP/NLP problems in a competitive amount of time. The results section discusses the performance of the algorithm and the effect of different operators by using a variety of MINLP/NLPs from different problem domains. © Springer-Verlag Berlin Heidelberg 2011.
• Optimization of Parallel Genetic Algorithms for nVidia GPUs

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  2011 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 803 - 811 2011 [Refereed][Not invited]
   

  Led by General Purpose computing over Graphical Processing Units (GPGPUs), the parallel computing area is witnessing a rapid change in dominant parallel systems. A major hurdle in this switch is the Single Instruction Multiple Thread (SIMT) architecture of GPUs which is usually not suitable for the design of legacy parallel algorithms. Genetic Algorithms (GAs) is no exception for that. GAs are commonly parallelized due to the high demanding computational needs. Given the performance of GPGPUs, the need to best exploit them to maximize computing efficiency for parallel GAs is demandingly growing. The goal of this paper is to shed light on the challenges parallel GAs designers/programmers will likely face while trying to achieve this, and to provide some practical advice on how to maximize GPGPU exploitation as a result. To that end, this paper provides a study on adapting legacy parallel GAs on GPGPU systems. The paper exposes the design challenges of nVidia's GPU architecture to the parallel GAs community by: discussing features of GPU, reviewing design issues in GPU relevant to parallel GAs, the design and introduction of new techniques to achieve an efficient implementation for parallel GAs and observing the effect of the pivotal points that both capitalize on the strengths of GPU and limit the deficiencies/overheads of GPUs. The paper demonstrates the performance of designed-for-GPGPU parallel GAs representing the entire spectrum of legacy parallel model of GAs over nVidia Tesla C1060 workstation showing a significant improvement in performance after optimizing and tuning the algorithms for GPU.
• Advanced Genetic Algorithm to solve MINLP problems over GPU

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  2011 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 318 - 325 2011 [Refereed][Not invited]
   

  In this paper we propose a many-core implementation of evolutionary computation for GPGPU (General-Purpose Graphic Processing Unit) to solve non-convex Mixed Integer Non-Linear Programming (MINLP) and non-convex Non Linear Programming (NLP) problems using a stochastic algorithm. Stochastic algorithms being random in their behavior are difficult to implement over GPU like architectures. In this paper we not only succeed in implementation of a stochastic algorithm over GPU but show considerable speedups over CPU implementations. The stochastic algorithm considered for this paper is an adaptive resolution approach to genetic algorithm (arGA), developed by the authors of this paper. The technique uses the entropy measure of each variable to adjust the intensity of the genetic search around promising individuals. Performance is further improved by hybridization with adaptive resolution local search (arLS) operator. In this paper, we describe the challenges and design choices involved in parallelization of this algorithm to solve complex MINLPs over a commodity GPU using Compute Unified Device Architecture (CUDA) programming model. Results section shows several numerical tests and performance measurements obtained by running the algorithm over an nVidia Fermi GPU. We show that for difficult problems we can obtain a speedup of up to 20x with double precision and up to 42x with single precision.
• Realizing Robust and Scalable Evolutionary Algorithms toward Exascale Era

  Masaharu Munetomo

  2011 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 312 - 317 2011 [Refereed][Not invited]
   

  Future trend of supercomputing goes toward exa flops, which is realized by millions of cores expected to be installed on around 2018. Such massive parallelism makes programming difficult. Inherent parallel nature of evolutionary computation is a promising factor in designing optimization algorithms that adapt to such massively parallel architecture although there are some problems to be solved to realize robust algorithm that can analyze complex interactions among genes. This paper discusses current status and future trend in realizing robust and scalable evolutionary computation on such extreme-scale supercomputers.
• Multi-level autonomic architecture for the management of virtualized application environments in cloud platforms

  Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama

  Proceedings - 2011 IEEE 4th International Conference on Cloud Computing, CLOUD 2011 754 - 755 2011 [Refereed][Not invited]
   

  Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological effects. Virtualization adds a greater flexibility to the resource manager in addressing such challenges. However, it imposes a further challenge of added management complexity. So, in this brief paper, we attempt to address still an open question of how to employ virtualization techniques effectively to realize a resource manager that intelligently adapts cloud platforms resource usage to satisfy the conflicting objectives of running applications and underlying cloud infrastructures by proposing a novel multi-level architecture which relays on a hybrid virtualization framework. We describe its functional components and dataflow and highlight the next steps that we will adopt in order to realize it and evaluate its feasibility and effectiveness. © 2011 IEEE.
• 北海道大学アカデミッククラウドにおけるコンテンツマネジメントシステムの展開

  情報処理学会第10回情報科学技術フォーラム論文集（査読付論文） RL-004  2011 [Not refereed][Not invited]
  
• A Framework for Problem-Specific QoS Based Scheduling in Grids

  Advances in Grid Computing 19 - 28 2011 [Not refereed][Not invited]
  
• An improved binary-real coded genetic algorithm for real parameter optimization

  Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama

  Proceedings of the 2011 3rd World Congress on Nature and Biologically Inspired Computing, NaBIC 2011 149 - 156 2011 [Not refereed][Not invited]
   

  Genetic algorithms (GAs) are vital members within the family biologically inspired algorithms. It has been proven that the performance of GAs is largely affected by the type of encoding schemes used to encode optimization problems. Binary and real encoding schemes are the most popular ones. However, it is still controversial to decide the superiority of one of them for GAs performance. Therefore, we have recently proposed binary-real coded GA (BRGA) that has the ability to use both encoding schemes at the same time. BRGA relays on a parameterized hybrid scheme to share the computational power and coordinate the cooperation between binary coded GA (BGA) and real coded GA (RGA). In this paper, we aim to evaluate the performance of BRGA systematically by utilizing CEC'2005 benchmark of 25 problems and adopting a robust experimental analysis approach. The quality and time performance of BRGA against the benchmark suite and in comparison with original component algorithms (BGA and RGA) is reported discussed and analyzed. Moreover, the performance of BRGA is compared with other Evolutionary Algorithms (EAs) from the literature. © 2011 IEEE.
• An adaptive resolution hybrid binary-real coded genetic algorithm

  Abdul-Rahman Omar Arif, Munetomo Masaharu, Akama Kiyoshi

  Artificial Life and Robotics Springer 16 (1) 121 - 124 1433-5298 2011 [Not refereed][Not invited]
   

  Which is better to be used in Genetic Algorithms (GAs) binary or floating point coding schemes? In this paper, we try to answer this controversial question by proposing a novel algorithm that shares the computational power between two cooperated versions of GAs, a binary coded GA (bGA) and a real coded GA (rGA). The evolutionary search is primarily led by bGA, which is used to identify promising regions in the search space. While, the rGA is used to increase the quality of the obtained solutions by conduct a detailed search through these regions. The interactions between two versions are organized by a resolution factor that it is increasingly adapted during the evolutionary search. Comparison experiments were conducted over a typica 1 function to proof the feasibility of the algorithm under critical scenarios of increasing problem dimensions and decreasing precision power.
• The design, usage, and performance of GridUFO: A Grid based Unified Framework for Optimization

  Munawar Asim, Wahib Mohamed, Munetomo Masaharu, Akama Kiyoshi

  Future Generation Computer Systems ELSEVIER 26 (4) 633 - 644 0167-739X 2010/04 [Not refereed][Not invited]
   

  We present GridUFO (Grid based Unified Framework for Optimization), a Service Oriented Architecture (SOA) compliant Problem Solving Environment (PSE) that allows the user to implement/share metaheuristics based optimization algorithms over a Grid. GridUFO eradicates the shortcomings of earlier projects and provides a unified approach for using algorithm/problem pair over a Grid in the easiest possible "plug & play" manner. This framework allows the users to concentrate on the actual application development, by hiding all the complexities involved in a Grid, without compromising on the functionality and flexibility promised by a Grid. This paper provides a detailed overview of the GridUFO infrastructure, specifically the way it deals with optimization algorithms and objective functions, handles Service Level Agreements (SLAs), and follows SOA. We also present various results achieved, that demonstrate both the utility and performance of GridUFO under various application workloads and scenarios. (C) 2009 Elsevier B.V. All rights reserved.
• A Light Framework for the Unified Representation and Execution of Variant Tasks in a Grid Based Environment.

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2010, Las Vegas, Nevada, USA, July 12-15, 2010, 2 Volumes CSREA Press 658 - 664 2010 [Refereed][Not invited]
  
• A Proposal for Zoning Crossover of Hybrid Genetic Algorithms for Large-scale Traveling Salesman Problems

  Masafumi Kuroda, Kunihito Yamamori, Masaharu Munetomo, Moritoshi Yasunaga, Ikuo Yoshihara

  2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 1 - 6 2010 [Refereed][Not invited]
   

  This paper proposes a novel crossover operator for solving large-scale traveling salesman problems (TSPs) by using a Hybrid Genetic Algorithm (HGA) with Lin-Kernighan heuristic for local search and we tentatively name Zoning Crossover (Z-Cross). The outline of Z-Cross is firstly to set a zone in the travelling area according to some rules, secondly to cut edges connecting cities between inside and outside the zone, thirdly to exchange edges inside the zone of one parent and those of the other parent, and lastly to reconnect sub-tours and isolated cities, which come about in the 3rd step mentioned above, so as to construct a new tour of TSP. The method is compared with conventional three crossovers; those are the Maximal Preservative Crossover, the Greedy Sub-tour Crossover and the Edge Recombination Crossover, and evaluated from the viewpoints of tour quality and CPU time. Ten benchmarks are selected from the well-known TSP website of Georgia Institute of Technology, whose names are xqf131, xqg237, ..., sra104815. The experiments are performed ten times for each crossover and each benchmark and show that the Z-Cross succeeds in finding better solution and running faster than the conventional methods. Six benchmarks with size from 39,603 to 104,815 cities are selected from the TSP website and challenged the records of tour lengths. The Z-Cross betters the record of the problem rbz43748 and approaches to solutions less than only 0.02% over the known best solutions for five instances.
• Live Migration-based Resource Managers for Virtualized Environments: A Survey

  Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama

  PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON CLOUD COMPUTING, GRIDS, AND VIRTUALIZATION (CLOUD COMPUTING 2010) 32 - 40 2010 [Not refereed][Not invited]
   

  Virtualization is a technology originally developed for mainframe computing. However, recent developments in the virtualization makes it a key technology to address the problems of modern distributed infrastructure like cloud platforms. Perhaps, one of the most important mechanisms provided by virtualization is the ability to migrate running applications without affecting the end user in a seamless manner. So, virtual machine migration is a promising approach to realize the objectives of efficient, adaptive and dynamic resource manager for virtualized environments. In this the paper, we present the state of art migration based resource managers for virtualized environments, compare and discuss different types of the underlying management algorithms from algorithmic issues standpoint.
• A Bayesian Optimization Algorithm For De Novo Ligand Design Based Docking Running Over GPU

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 17 - 24 2010 [Not refereed][Not invited]
   

  A principal fragment-based design approach is De Novo ligand design at which small-molecule structures from a database of existing compounds (or compounds that could be made) are docked into the protein binding site following a virtual synthesis scheme. New virtual structures can easily be constructed from combinatorial building blocks. Typically, tens of thousands of orientations are generated for each ligand candidate, therefore global optimization algorithms are usually employed to search the chemical space by generating new molecular structures through probing many different fragments in a combinatorial fashion. We propose using Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, in searching the combination of pre-docked fragments through minimizing the energy of ligand-receptor docking. We further introduce the use of GPU (Graphical Processing Unit) to overcome the very long time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragments and target receptors for more complex instances. The experiments resulted in regenerating three drug-like compounds defined in the ZINC database as well as finding a new compound. The Results show how the nVidia's Tesla C1060 GPU was utilized to accelerate the docking process by two orders of magnitude.
• Development of a Novel Crossover of Hybrid Genetic Algorithms for Large-scale Traveling Salesman Problems

  Proceedings of the Fifteenth International Symposium on Artificial Life and Robotics 2010 828 - 831 2010 [Not refereed][Not invited]
  
• Implementation and Optimization of cGA+LS to solve Capacitated VRP over Cell/B.E.

  Munawar Asim, Wahib Mohamed, Munetomo Masaharu, Akama Kiyoshi

  International Journal of Advancements in Computing Technology Advanced Institute of Convergence IT 1 (2) 16 - 28 2005-8039 2009/12 [Not refereed][Not invited]
   

  This paper presents a case study to illustrate the design and implementation of cellular Genetic Algorithm (cGA) with Local Search (LS) to solve Capacitated Vehicle Routing Problem (CVRP) over Cell Broadband Engine (Cell BE). Cell BE is a heterogeneous, distributed memory multicore processor architecture for multimedia applications with regular memory access requirements. It has one 64-bit Power Processing Element (PPE) that acts as the main processor and 8 Synergistic Processing Elements (SPEs) with only 256 KB of local memory, each for instructions and data. GAs on the other hand use popu...
• An automated ligand evolution system using Bayesian optimization algorithm

  Munetomo Masaharu, Akama Kiyoshi, Maeda Haruki

  WSEAS Transactions on Information Science and Applications World Scientific and Engineering Academy and Society 6 (5) 788 - 797 1790-0832 2009/05 [Not refereed][Not invited]
   

  Ligand docking checks whether a drug chemical called ligand matches the target receptor protein of human organ or not. Docking by computer simulation is becoming popular in drug design process to reduce cost and time of the chemical experiments. This paper presents a novel approach generating optimal ligand structures from scratch based on de novo ligand design approach employing Bayesian optimization algorithm to realize an automated design of drug and other chemical structures. The proposed approach searches an optimal structure of ligand that minimizes bond energy to the receptor protein...
• Theoretical and Empirical Analysis of a GPU based Parallel Bayesian Optimization Algorithm

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  2009 INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT 2009) 457 - + 2009 [Refereed][Not invited]
   

  General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelization of Bayesian Optimization Algorithm (BOA) to solve complex combinatorial optimization problems over nVidia commodity graphics hardware using Compute Unified Device Architecture (CUDA). BOA is a well-known multivariate Estimation of Distribution Algorithm (EDA) that incorporates methods for learning Bayesian Network (BN). It then uses BN to sample new promising solutions. Our implementation is fully compatible with modern commodity GPUs and therefore we call it gBOA (BOA on GPU). In the results section, we show several numerical tests and performance measurements obtained by running gBOA over an nVidia Tesla C1060 GPU. We show that in the best case we can obtain a speedup of up to 13x.
• Theoretical and Empirical Analysis of a GPU based Parallel Bayesian Optimization Algorithm

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  2009 INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT 2009) 457 - + 2009 [Not refereed][Not invited]
   

  General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelization of Bayesian Optimization Algorithm (BOA) to solve complex combinatorial optimization problems over nVidia commodity graphics hardware using Compute Unified Device Architecture (CUDA). BOA is a well-known multivariate Estimation of Distribution Algorithm (EDA) that incorporates methods for learning Bayesian Network (BN). It then uses BN to sample new promising solutions. Our implementation is fully compatible with modern commodity GPUs and therefore we call it gBOA (BOA on GPU). In the results section, we show several numerical tests and performance measurements obtained by running gBOA over an nVidia Tesla C1060 GPU. We show that in the best case we can obtain a speedup of up to 13x.
• An Automated Ligand Evolution System using Bayesian Optimization Algorithm

  WSEA Transactions on Information Science and Applications 6 (5) 788 - 797 2009 [Not refereed][Not invited]
  
• De Novo Ligand Evolution using Bayesian Optimization Algorithms

  Proceedings of the 10th WSEAS International Conference on Evolutionary Computing 126 - 131 2009 [Not refereed][Not invited]
  
• Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA framework

  Munawar Asim, Wahib Mohamed, Munetomo Masaharu, Akama Kiyoshi

  Genetic Programming and Evolvable Machines Springer 10 (4) 391 - 415 1389-2576 2009 [Not refereed][Not invited]
   

  General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelizing a hybrid of Genetic Algorithm (GA) and Local Search (LS) to solve MAXimum SATisfiability (MAX-SAT) problem on a state-of-the-art nVidia Tesla GPU using nVidia Compute Unified Device Architecture (CUDA). MAX-SAT is a problem of practical importance and is often solved by employing metaheuristics based search methods like GAs and hybrid of GA with LS. Almost all the parallel GAs (pGAs) designed in the last two decades were designed for either clusters or MPPs. Unfortunately, very little research is done on the implementation of such algorithms over commodity graphics hardware. GAs in their simple form are not suitable for implementation over the Single Instruction Multiple Thread (SIMT) architecture of a GPU, and the same is the case with conventional LS algorithms. In this paper we explore different genetic operators that can be used for an efficient implementation of GAs over nVidia GPUs. We also design and introduce new techniques/operators for an efficient implementation of GAs and LS over such architectures. We use nVidia Tesla C1060 to perform several numerical tests and performance measurements and show that in the best case we obtain a speedup of 25x. We also discuss the effects of different optimization techniques on the overall execution time.
• Introducing assignment functions to Bayesian optimization algorithms

  Munetomo Masaharu, Murao Naoya, Akama Kiyoshi

  Information Sciences Elsevier Inc. 178 (1) 152 - 163 0020-0255 2008/01/02 [Not refereed][Not invited]
   

  In this paper, we improve Bayesian optimization algorithms by introducing proportionate and rank-based assignment functions. A Bayesian optimization algorithm builds a Bayesian network from a selected sub-population of promising solutions, and this probabilistic model is employed to generate the offspring of the next generation. Our method assigns each solution a relative significance based on its fitness, and this information is used in building the Bayesian network model. These assignment functions can improve the quality of the model without performing an explicit selection on the population. Numerical experiments demonstrate the effectiveness of this method compared to a conventional BOA. (C) 2007 Elsevier Inc. All rights reserved.
• Model for Dynamic Grain Sizing Through Compound Parallelization for an Optimization Problem Solving Grid Application

  M. Wahib, Asim Munawar, Masaharu Munetomo, Akama Kiyoshi

  2008 9TH IEEE/ACM INTERNATIONAL CONFERENCE ON GRID COMPUTING 316 - + 2008 [Not refereed][Not invited]
   

  MHGrid (Meta Heuristics Grid), a service oriented grid application offering global optimization solvers, allows developers to integrate their solvers and objective functions through an easy-to-use transparent mechanism. As a consequence of offering such a service, MHGrid hosts solvers and objective functions implementing diverse parallelization models leading later to different job grain size. Yet, the flexibility of the existing grid programming tools is limited if used individually. This paper proposes a model that uses a combination of grid parallel programming tools to enable the developers of MHGrid to specify their own parallelization model. Using this model the end user can choose the parallel model of the solver/objective function pair generating the grain size most appropriate to the problem in hand.
• SOAG: Service Oriented Architectured Grids and Adoption of Application specific QoS Attributes

  M. Wahib, Asim Munawar, Masaharu Munetomo, Akama Kiyoshi

  2008 9TH IEEE/ACM INTERNATIONAL CONFERENCE ON GRID COMPUTING 346 - + 2008 [Not refereed][Not invited]
   

  Since the introduction of grid computing various efforts were directed towards integrating and combining the grid with SOA technologies. That was mainly motivated by capitalizing on the widely desirable properties of SOA technologies. Nevertheless, the combination of SOA with grid computing in real practice is mainly tangible in the alignment of grid technologies with Web services. Therefore the effects were merely noticeable in the application layer and were more likely to define a SOA model for inner components' interactions. The deficient combination of grid with SOA needs to be deeply investigated to reach a comprehensive integration of grid with SOA that starts from the application layer till lower grid middleware layers. A major impact in this integration is offering application layer functionalities as services and thus having application specific QoS attributes originating from the application layer to be included in job scheduling. This paper presents integrating Grid computing with SOA into a generic Service Oriented Architecutered Grid (SOAG) model. A SOAG model for MHGrid -a service-oriented grid application for solving global optimization problems-is also briefly introduced.
• Solving Large Instances of Capacitated Vehicle Routing Problem over Cell BE

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  HPCC 2008: 10TH IEEE INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS, PROCEEDINGS 131 - + 2008 [Not refereed][Not invited]
   

  This paper presents a method to solve large instances of Capacitated Vehicle Routing Problem (CVRP) using Cellular Genetic Algorithm (cGA) with Local Search (LS) over Cell Broadband Engine (Cell BE) architecture. We propose a unique parallelization model where computationally intensive Local Search (LS) runs on the available Synergistic Processing Elements (SPEs) in parallel, while the Power Processor Element (PPE) runs the cGA and acts as a controller for all the SPEs. We reproduce the results from earlier work in PPE only implementation of the algorithm, and we show a considerable reduction in execution time for parallel implementation over Cell BE. Moreover we extended it further to solve larger instances of CVRP (compared to the ones present in the CVRP literature), and got acceptable results in a reasonable amount of time.
• A Survey: Genetic Algorithms and the Fast Evolving World of Parallel Computing

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  HPCC 2008: 10TH IEEE INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS, PROCEEDINGS 897 - + 2008 [Not refereed][Not invited]
   

  This paper gives a survey about the impact of modern parallel/distributed computing paradigms over Parallel Genetic Algorithms (PGAs). Helping the GA community to feel more comfortable with the evolving parallel paradigms, and marking some areas of research for the High-Performance Computing (HPC) community is the major inspiration behind this survey. In the modern parallel computing paradigms we have considered only two major areas that have evolved very quickly during the past few years, namely, multicore computing and Grid computing. We discuss the challenges involved, and give potential solutions for these challenges. We also propose a hierarchical PGA suitable for Grid environment with multicore computational resources.
• A General Service-Oriented Grid Computing Framework For Global Optimization Problem Solving

  M. Wahib, Asim Munawar, Masaharu Munetomo, Akama Kiyoshi

  2008 IEEE INTERNATIONAL CONFERENCE ON SERVICES COMPUTING, PROCEEDINGS, VOL 2 563 - + 2008 [Not refereed][Not invited]
   

  MetaHeuristics Grid (MHGrid) is a service oriented Grid application that enables the user to solve almost any global optimization problem using metaheuristics techniques. Two problems potentially limit the generality of MHGrid over the problem type space; having a fixed set of solvers and lacking the solver-problem relation semantics. The set of strategies enforced to resolve these two problems are: offering the solvers as services, enabling the user to define his parallelization model, allowing the user to add his own service and maintaining service-based functionalities on both the middleware layer and application layer This paper explains the design, architecture and implementation of the SOA that MHGrid endorses that would allow the enforcing of the resolving strategies.
• Empirical Investigations on Parallel Competent Genetic Algorithms

  Proceedings of the 2008 Genetic and Evolutionary Computation Conference 1073 - 1080 2008 [Not refereed][Not invited]
  
• Linkage Identification in Evolutionary Computation(New Development in Evolutionary Computation)

  MUNETOMO Masaharu

  SYSTEMS, CONTROL AND INFORMATION システム制御情報学会 52 (10) 362 - 367 0916-1600 2008 [Not refereed][Not invited]
   

  「進化計算の新展開特集号」解説
• Parallel GEAs with linkage analysis over grid

  Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama

  Studies in Computational Intelligence 157 159 - 187 1860-949X 2008 [Refereed][Not invited]
   

  This chapter describes the latest trends in the field of parallel/ distributed computing and the effect of these trends over Genetic and Evolutionary Algorithms (GEAs) especially linkage based GEAs. We concentrate mainly on the Grid computing paradigm which is widely accepted as the most distributed form of computing due to the advent of Service Oriented Architecture (SOA) and other technologies, Grid has gained a lot of attention in the recent years. We also present a framework that can help users in implementation of metaheuristics based optimization algorithms (including GEAs) over a Grid computing environment. We call this framework MetaHeuristics Grid (MHGrid). Moreover, we give a theoretical analysis of the maximum speed-up achievable by using MHGrid. We also discuss our experience of working with Grids. © 2008 Springer-Verlag Berlin Heidelberg.
• A network design problem by a GA with linkage identification and recombination for overlapping building blocks

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  Studies in Computational Intelligence 157 441 - 459 1860-949X 2008 [Refereed][Not invited]
   

  Efficient mixing of building blocks is important for genetic algorithms and linkage identification methods that identify interdependent variables tightly linked to form a building block have been proposed. However, they have not been applied to real-world problems enough. In this chapter, we apply a genetic algorithm incorporating a linkage identification method called D5 and a crossover method called CDC to a network design problem to verify its performance and examine the applicability of linkage identification genetic algorithms. © 2008 Springer-Verlag Berlin Heidelberg.
• Linkage analysis in genetic algorithms

  Miwako Tsuji, Masaharu Munetomo

  Studies in Computational Intelligence 137 251 - 279 1860-949X 2008 [Refereed][Not invited]
   

  A series of advanced techniques in genetic and evolutionary computation have been proposed that analyze gene linkage to realize competent genetic algorithms. Although it is important to encode linked variables tightly for simple GAs, it is sometimes difficult because it requires enough knowledge of problems to be solved. In order to solve real-world problems effectively even if the knowledge is not available, we need to analyze gene linkage. We review algorithms which have been proposed that identify linkage by applying perturbations, by building a probabilistic model of promising strings, and a recombination of the both of the above. We also introduce a context-dependent crossover that can utilize overlapping linkage information in a sophisticated manner. By employing linkage identification techniques with context dependent crossover, we can solve practical real-world application problems that usually have complex problem structures without knowing them before optimization. © 2008 Springer-Verlag Berlin Heidelberg.
• 複雑なビルディングブロック重複を持つ問題に対する交叉手法の提案

  辻 美和子, 棟朝 雅晴, 赤間 清

  情報処理学会論文誌. 数理モデル化と応用 一般社団法人情報処理学会 48 (15) 23 - 33 0387-5806 2007/10/15 [Not refereed][Not invited]
   

  遺伝的アルゴリズムによる効率的な探索のために,同一のビルディングブロック(building block, BB)を構成する遺伝子座の集合を検出する手法は多く提案されている(Heckendornら).しかしながら,これらの手法から得られたリンケージ情報を利用して効果的に交叉を行う方法については,十分な検討がなされてこなかった.特に重複するBBを持つ問題ではYuら(2005)の交叉手法のみが知られている.しかし,彼らの手法はBBの重複構造が複雑になったとき,頻繁にBBを破壊し,かつ十分な交叉パターンが得られないために,効率的に機能しない.本論文では,Yuらの手法を拡張し,BB破壊をできるだけ抑えながら,新たな異なる探索点を与える交叉手法を提案する.提案される手法は,コンテクスト依存交叉(Context Dependent Crossover, CDC)と呼ばれ,与えられた親個体組の値を調査したうえで,交換する遺伝子座を決定する.CDCは,リンケージ同定手法と併用されることで,重複するBBを持つ問題を探索する強力なアルゴリズムを提供する.また,提案手法の性能を確認するために,重複の複雑さが制御可能なテスト関数を設計する.
• MHGrid: Towards an ideal optimization environment for global optimization problems using Grid computing

  M. Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  EIGHTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PROCEEDINGS 167 - + 2007 [Not refereed][Not invited]
  
• 複雑なビルディングブロック重複を持つ問題に対する交叉手法の提案

  情報処理学会論文誌「数理モデル化と応用」 48 (SIG15) 23 - 33 2007 [Not refereed][Not invited]
  
• Optimization problem solving framework employing GAs with linkage identification over a Grid environment

  Asim Munawar, Masaharu Munetomo, Kiyoshi Akama

  2007 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-10, PROCEEDINGS 1191 - + 2007 [Not refereed][Not invited]
   

  This paper is a step towards a general purpose optimization problem-solving framework that can solve a large number of global optimization problems on its own with a minimal input from the user. It relies on competent GAs (Genetic Algorithms) as the solver and depends on Grid computing for the required computational resources. In this paper we will discuss the architecture of the framework in detail. In the results section we will discuss the speedups obtained by using parallel GAs over a Grid computing environment and the effects of Grid overheads on the speedup. Even though there are various advantages of using Grids but in the results section we will focus on the reduction in total execution time due to parallelism.
• A network design problem by a GA with linkage identification and recombination for overlapping building blocks

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  2007 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-10, PROCEEDINGS 349 - 356 2007 [Not refereed][Not invited]
   

  Efficient mixing of building blocks is important for genetic algorithms and linkage identification that identify variables tightly linked to form a building block have been proposed. In this paper, we apply D-5-GA with CDC - a genetic algorithm incorporating a linkage identification method called D-5 and a crossover method called CDC - to a network design problem to verify its performance and examine the applicability of the linkage identification genetic algorithms.
• Standardization of Interfaces for Meta-Heuristics based Problem Solving Framework over Grid Environment

  Proceedings of the HPC Asia 2007 129 - 136 2007 [Not refereed][Not invited]
  
• On Hybridization of Bayesian Optimization and Tabu Search

  Proceedings of the Seventh Metaheuristics International Conference (CD-ROM) 52  2007 [Not refereed][Not invited]
  
• An intelligent scatter with estimation of distribution for tabu search

  Masaharu Munetomo, Yuta Satake, Kiyoshi Akama

  COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 465 - + 0302-9743 2007 [Not refereed][Not invited]
   

  This paper proposes an efficient optimization algorithm based on tabu search and estimation of distribution algorithms. The proposed algorithm estimates characteristics of distribution of solutions after performing tabu searches based on a marginal product model to acquire linkage information. Once correct linkage information is obtained, we can perform crossovers effectively without disrupting building blocks using the information. The proposed algorithm is expected to adapt to both global and local characteristics of solution space. Through empirical studies, we show the effectiveness of our approach.
• A framework of GRID problem-solving environment employing robust evolutionary search

  Masaharu Munetomo, Asim Munawar, Kiyoshi Akama

  COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 473 - + 0302-9743 2007 [Not refereed][Not invited]
   

  This paper presents a problem-solving framework based on robust evolutionary search in GRID computing environment. Our problem-solving environment called virtual innovative laboratory performs simulator programs in parallel and optimize their input parameters employing a competent evolutionary algorithm with gene analysis. The objective of our project is to replace a part of human designer's try-and-error processes by a parallel and robust evolutionary search on GRID computing systems.
• An intelligent scatter with estimation of distribution for tabu search

  Masaharu Munetomo, Yuta Satake, Kiyoshi Akama

  COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 465 - + 0302-9743 2007 [Not refereed][Not invited]
   

  This paper proposes an efficient optimization algorithm based on tabu search and estimation of distribution algorithms. The proposed algorithm estimates characteristics of distribution of solutions after performing tabu searches based on a marginal product model to acquire linkage information. Once correct linkage information is obtained, we can perform crossovers effectively without disrupting building blocks using the information. The proposed algorithm is expected to adapt to both global and local characteristics of solution space. Through empirical studies, we show the effectiveness of our approach.
• A framework of GRID problem-solving environment employing robust evolutionary search

  Masaharu Munetomo, Asim Munawar, Kiyoshi Akama

  COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 473 - + 0302-9743 2007 [Not refereed][Not invited]
   

  This paper presents a problem-solving framework based on robust evolutionary search in GRID computing environment. Our problem-solving environment called virtual innovative laboratory performs simulator programs in parallel and optimize their input parameters employing a competent evolutionary algorithm with gene analysis. The objective of our project is to replace a part of human designer's try-and-error processes by a parallel and robust evolutionary search on GRID computing systems.
• On Hybridization of Bayesian Optimization and Tabu Search

  Proceedings of the Seventh Metaheuristics International Conference (CD-ROM) 52  2007 [Not refereed][Not invited]
  
• Genetic algorithm to optimize fitness function with sampling error and its application to financial optimization problem

  Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama

  Studies in Computational Intelligence 51 417 - 434 1860-949X 2007 [Refereed][Not invited]
   

  Fitness function of financial optimization problem is often evaluated by Monte-Carlo method which is based on stochastic sampling. In this chapter we deal with the trade-off between the accuracy of the fitness estimation and its computational overheads, and introduce a method to decide the number of samples that maximizes the efficiency of genetic algorithms for financial problems. We define an index called selection efficiency which shows how close the population approaches to takeover in a fixed amount of time. When selection efficiency is maximized, the population converges to good solution rapidly, and optimization progresses most efficiently. Selection efficiency is generally difficult to calculate analytically. Thus bootstrapping approach is employed to calculate selection efficiency. The method estimates selection efficiency from the empirical distribution. The method is applied to the optimization of the procurement plan problem, and it optimizes Value at Risk efficiently. © Springer-Verlag Berlin Heidelberg 2007.
• Linkage identification by fitness difference clustering

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  Evolutionary Computation 14 (4) 383 - 409 1063-6560 2006/12 [Not refereed][Not invited]
   

  Genetic Algorithms perform crossovers effectively when linkage sets -sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D5), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs. © 2006 by the Massachusetts Institute of Technology.
• Linkage identification by fitness difference clustering

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  Evolutionary Computation 14 (4) 383 - 409 1063-6560 2006/12 [Refereed][Not invited]
   

  Genetic Algorithms perform crossovers effectively when linkage sets -sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D5), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs. © 2006 by the Massachusetts Institute of Technology.
• Linkage Identification for Real-coded Genetic Algorithms Based on Additive Decomposability and Difference Signature Independency of Objective Function

  TEZUKA MASARU, MUNETOMO MASAHARU, AKAMA KIYOSHI

  情報処理学会論文誌数理モデル化と応用（TOM） 一般社団法人情報処理学会 47 (14) 43 - 53 1882-7780 2006/10/15 [Not refereed][Not invited]
   

  In the case that a problem is decomposable to a number of sub-problems which can be optimized independently, the problem is solved effectively by optimizing sub-problems separately. In optimization problems by means of genetic algorithms, a set of loci of which each sub-problem consists is called linkage group. Linkage identification is the method which recognizes linkage groups. In this paper, we define the linkage of Real-Coded GAs clearly. Then we propose two new linkage identification methods, LINC-R and LIDI-R, directly based on the definition. LINC-R is based on additive decomposability and LIDI-R is based on independency of the signature of difference of an objective function. These methods effectively identify linkages.
• Linkage Identification for Real-coded Genetic Algorithms Based on Additive Decomposability and Difference Signature Independency of Objective Function

  TEZUKA MASARU, MUNETOMO MASAHARU, AKAMA KIYOSHI

  情報処理学会論文誌. 数理モデル化と応用 一般社団法人情報処理学会 47 (14) 43 - 53 0387-5806 2006/10/15 [Not refereed][Not invited]
   

  In the case that a problem is decomposable to a number of sub-problems which can be optimized independently, the problem is solved effectively by optimizing sub-problems separately. In optimization problems by means of genetic algorithms, a set of loci of which each sub-problem consists is called linkage group. Linkage identification is the method which recognizes linkage groups. In this paper, we define the linkage of Real-Coded GAs clearly. Then we propose two new linkage identification methods, LINC-R and LIDI-R, directly based on the definition. LINC-R is based on additive decomposabili...
• Risk Visualization and Decision Support for Supply Planning under Uncertain Demand

  TEZUKA MASARU, HIJI MASAHIRO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  IPSJ journal 一般社団法人情報処理学会 47 (3) 701 - 710 1882-7764 2006/03/15 [Not refereed][Not invited]
   

  In recent years, the life-cycle of high-tech products such as personal computers and cellular phones is getting shortened. Shorter life-cycle makes the risk of opportunity loss and dead-stock disposal loss higher. Supply plan designates the quantity and the delivery date of products to supply. The plan is created based on forecasted demand in order to cover the demand. Statistical method is used to forecast, however, shorter life-cycle also makes it difficult to obtain enough amounts of historical record to conduct statistical analysis. Consequently, the forecast accuracy declines. Since the decision made on the supply plan has a greater impact on the profitability these days, the decision based on quantitative evaluation is essential to manufacturers and resellers. In this paper, the model which explains how the profit is produced from the demand and supply is constructed. Taking advantage of the model, gross profit, opportunity loss, and dead-stock disposal loss are analyzed with Monte-Carlo method and evaluated quantitatively. The application of the proposed system on two cases shows the effectiveness of the system.
• Risk Visualization and Decision Support for Supply Planning under Uncertain Demand(Information Systems for Society and Humans,Information Systems for New Application Domains)

  TEZUKA MASARU, HIJI MASAHIRO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  IPSJ Journal 一般社団法人情報処理学会 47 (3) 701 - 710 0387-5806 2006/03/15 [Not refereed][Not invited]
   

  In recent years, the life-cycle of high-tech products such as personal computers and cellular phones is getting shortened. Shorter life-cycle makes the risk of opportunity loss and dead-stock disposal loss higher. Supply plan designates the quantity and the delivery date of products to supply. The plan is created based on forecasted demand in order to cover the demand. Statistical method is used to forecast, however, shorter life-cycle also makes it difficult to obtain enough amounts of historical record to conduct statistical analysis. Consequently, the forecast accuracy declines. Since th...
• Realizing Virtual Innovative Laboratory with Robust Evolutionary Algorithms over the GRID computing system

  Proceedings of the 6th International Conference on Recent Advance in Soft Computing 42 - 47 2006 [Not refereed][Not invited]
  
• A crossover for complex building blocks overlapping

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2 1337 - + 2006 [Not refereed][Not invited]
   

  We propose a crossover method to combine complexly overlapping building blocks (BBs). Although there have been several techniques to identify linkage sets of loci o form a BB [4, 6, 7, 10, 11], the way to to realize effective crossover from the linkage information from such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu et al. [13] is the first and only known research, however it cannot perform well for problems with complexly overlapping BBs due to insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings minutely and defines which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. The method is combined with a scalable linkage identification technique to construct an efficient algorithm for problems with overlapping BBs. We design test functions with controllable complexity of overlap and test the method with the functions.
• Control the Number of Samples to Estimate Fitness from the Perspective of Takeover Time and Optimization of Financial Criteria

  Proceedings of the 2006 IEEE Congress on Evolutionary Computation 388 - 394 2006 [Not refereed][Not invited]
  
• Enhancing model-building efficiency in extended compact genetic algorithms

  Masaharu Munetomo, Yuta Satake, Kiyoshi Akama

  2006 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-6, PROCEEDINGS 2362 - + 1062-922X 2006 [Not refereed][Not invited]
   

  Probabilistic model-building genetic algorithms such as extended compact genetic algorithm (ECGA) are proposed to solve difficult problems for classical genetic algorithms. Probabilistic model-building process based on marginal product model needs extensive computational overheads in ECGA. This paper discusses ECGA with linkage re-utilization and local search to reduce its model-building cost. Through simulation studies, we show the effectiveness of our approach that can reduce overall computational overheads.
• Theoretical and empirical investigations on difficulty in structure learning by estimation of distribution algorithms

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  2006 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-6, PROCEEDINGS 209 - + 1062-922X 2006 [Not refereed][Not invited]
   

  Estimation of distribution algorithms (EDAs) are population based evolutionary algorithms derived from genetic algorithms (GAs). EDAs build probabilistic models of promising solutions to guide further exploration of the search space. They have been considered to behave in similar way to GAs. In this paper, we show their different behaviors and difficulties in applications of EDAs by designing an EDA difficult function in which schemata that are not consistent with problem structure sometimes overwhelm those that are.
• Genetic algorithm to optimize fitness function with sampling error and its application to financial optimization problem

  Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama, Masahiro Hiji

  2006 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-6 81 - 87 2006 [Refereed][Not invited]
   

  In this paper we discuss the optimization problems with noisy fitness function. On financial optimization problems, Monte-Carlo method is commonly used to evaluate the optimization criteria such as value at risk. The evaluation model is often very complex which needs considerable computational overheads. In order to realize efficient optimization of financial problems, we propose a method to decide the number of samples used to estimate the optimization criteria. Selection efficiency proposed in this paper is a index that shows how close the population approaches to the convergence to a good solution. In general, it is difficult to calculate selection efficiency analytically. Thus we also employ bootstrap method to estimate selection efficiency. The resulting algorithm is applied to the optimization of the procurement plan optimization problem. The result shows that Value at Risk of the problem is optimized efficiently by the proposed method.
• Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama: "Population Sizing of Dependency Detection by Fitness Difference Classification", Foundations of Genetic Algorithms - FOGA2005, Lecture Notes in Computer Science 3469:282-299 (2005)*

  2005 [Not refereed][Not invited]
  
• Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama: "Linkage Identification for Real-Values Loci by Fitness Difference Classification", Proceedings of 2005 Congress on Evolutionary Computation, 2:1317-1324 (2005)*

  2005 [Not refereed][Not invited]
  
• Masaharu Munetomo, Naoya Murao, Kiyoshi Akama: "Empirical Studies on Parallel Network Construction of Bayesian Optimization Algorithms", Proceedings of 2005 Congress on Evolutionary Computation, 2:1524-1531 (2005)*

  2005 [Not refereed][Not invited]
  
• Empirical studies on parallel network construction of Bayesian optimization algorithms

  M Munetomo, N Murao, K Akama

  2005 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-3, PROCEEDINGS 1524 - 1531 2005 [Refereed][Not invited]
   

  This paper discusses a parallel optimization algorithm based on evolutionary algorithms with probabilistic model-building in order to design a robust search algorithm that can be applicable to a wide-spectrum of application problems effectively and reliably. Probabilistic model building genetic algorithm, which is also called estimation of distribution algorithm, is a promising approach in evolutionary computation and its parallelization has been investigated. We propose an improvement of parallel network construction in distributed Bayesian optimization algorithms which estimate distribution of promising solutions as Bayesian networks. Through numerical experiments on an actual parallel architecture, we show the effectiveness of our approach compared to the conventional parallelization. Also we perform experiments on a real-world application problem: protein structure predictions.
• Linkage identification for real-valued loci by fitness difference classification

  M Tsuji, M Munetomo, K Akama

  2005 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-3, PROCEEDINGS 1317 - 1324 2005 [Refereed][Not invited]
   

  In order to enhance efficiency of genetic algorithms, it is important to identify a linkage set, i.e. a set of loci tightly linked to construct a building block. In this paper, we propose a novel linkage identification method for real-valued strings called the real-valued Dependency Detection for Distribution Derived from df (rD(5)). It can detect linkage sets with quasi-linear fitness evaluations. The rD(5) is designed based on the D-5 which has been proposed for binary strings. It detects dependencies of loci by estimating the distribution of strings classified according to fitness differences. The rD(5) and the LINC-R which is one of linkage identification methods proposed elsewhere, provide approximate equivalent information about a function to be solved, however, the rD(5) performs smaller number of fitness evaluations than the LINC-R for larger functions. Although estimation of distribution algorithms (EDAs) also estimate distribution of strings, it is difficult for EDAs to solve a function composed of exponentially scaled sub-functions. The proposed method, by contrast, can be applied to the function in the similar way to as to a function composed of uniformly scaled sub-functions which is easy for EDAs. We perform experiments to compare the proposed method with the LINC-R and to examine the scaling effect stability of the rD(5). We also investigate two parameters, that define the amount of perturbation (mutation) and that define the quantization level.
• Population sizing of dependency detection by fitness difference classification

  M Tsuji, M Munetomo, K Akama

  FOUNDATIONS OF GENETIC ALGORITHMS 3469 282 - 299 0302-9743 2005 [Refereed][Not invited]
   

  Recently, the linkage problem has attracted attention from researchers and users of genetic algorithms and many efforts have been undertaken to learn linkage. Especially, (1) perturbation methods (PMs) and (2) estimation of distribution algorithms (EDAs) are well known and frequently employed for linkage identification. In our previous work [TMA04], we have proposed a novel approach called Dependency Detection for Distribution Derived from df (D-5) which inherits characteristics from both EDAs and PMs. It detects dependencies of loci by estimating the distributions of strings classified according to fitness differences and can solve EDA difficult problems requiring a smaller number of fitness evaluations. In this paper, we estimate population size for the D5 and its computation cost. The computation cost slightly exceeds O(l), which is less than the PMs and some of EDAs.
• Multi-objective Real-coded Genetic Algorithm Approach for Supply Planning Under Uncertainty

  TEZUKA MASARU, HIJI MASAHIRO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  IPSJ journal 一般社団法人情報処理学会 45 (10) 2287 - 2296 1882-7764 2004/10/15 [Not refereed][Not invited]
   

  Supply is planned to meet the future forecast. However, uncertainty is involeved in the supply plan since it is difficult to forecast the future demand accurately. The impact to business caused by the gap between the forecast and actual demand is called risk. Thus, supply planning methods which can maximize profit and minimize risk simultaneously is desired. The conventional method based on safety stock or buffer stock has been widely used, whose main purpose is to prevent the occurrence of opportunity loss. In order to simulate the uncertainty and evaluate the profit and risk, we introduced Monte Carlo simulation. According to the fitness calculated by the simulation, a genetic algorithm optimizes the profit, risk, opportunity loss, and final inventory quantity of supply planning problems. The approach was tested on the supply planning data and has achieved a remarkable result.
• Multi-objective Real-coded Genetic Algorithm Approach for Supply Planning Under Uncertainty(Applications of Information Systems to Society and Interprises)

  TEZUKA MASARU, HIJI MASAHIRO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  IPSJ Journal 一般社団法人情報処理学会 45 (10) 2287 - 2296 0387-5806 2004/10/15 [Not refereed][Not invited]
   

  Supply is planned to meet the future forecast. However, uncertainty is involeved in the supply plan since it is difficult to forecast the future demand accurately. The impact to business caused by the gap between the forecast and actual demand is called risk. Thus, supply planning methods which can maximize profit and minimize risk simultaneously is desired. The conventional method based on safety stock or buffer stock has been widely used, whose main purpose is to prevent the occurrence of opportunity loss. In order to simulate the uncertainty and evaluate the profit and risk, we introduce...
• Linkage Identification for Problems with Hierarchical Structure

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  情報処理学会論文誌数理モデル化と応用（TOM） 一般社団法人情報処理学会 45 (2) 22 - 31 1882-7780 2004/02/15 [Not refereed][Not invited]
   

  To avoid building block destructions, linkage identification techniques are proposed, which tries to identify a set of loci tightly-linked explicitly before performing genetic optimizations. Real-world problems, especially large-scaled complex problems, sometimes take hierarchical structures in which building blocks have recursive interdependencies. Existing linkage identification algorithms only consider interactions between loci in a same building block and assume no interdependency between building blocks. In this paper, the LIEM2 (Linkage Identification with Epistasis Measure considering Monotonicity) - a single layer linkage identification algorithm based on non-monotonicity conditions - is extended to identify hierarchical multi-layered linkage groups in order to search more accurate structures of real-world problems. The hierarchical linkage identification identifies linkage groups hierarchically in a recursive manner employing niching which preserve various building block candidates.
• Linkage Identification for Problems with Hierarchical Structure (Theory)(Evolutionary Computation)

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  情報処理学会論文誌. 数理モデル化と応用 一般社団法人情報処理学会 45 (2) 22 - 31 0387-5806 2004/02/15 [Not refereed][Not invited]
   

  To avoid building block destructions, linkage identification techniques are proposed, which tries to identify a set of loci tightly-linked explicitly before performing genetic optimizations. Real-world problems, especially large-scaled complex problems, sometimes take hierarchical structures in which building blocks have recursive interdependencies. Existing linkage identification algorithms only consider interactions between loci in a same building block and assume no interdependency between building blocks. In this paper, the LIEM2 (Linkage Identification with Epistasis Measure considerin...
• Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama: Selection Efficiency and Sampling Error on Genetic Algorithms Optimization under Uncertainty, Proceedings of 2004 Simulated Evolution and Learning (SEAL2004), (CD-ROM) (2004)*

  2004 [Not refereed][Not invited]
  
• Masaharu Munetomo, Naoya Murao, Kiyoshi Akama: "Empirical Investigations on Parallelized Linkage Identification", Parallel Problem Solving from Nature - PPSN VIII, Lecture Notes in Computer Science, 3242:322-331 (2004)*

  2004 [Not refereed][Not invited]
  
• Naoya Murao, Masaharu Munetomo, Kiyoshi Akama: "Performance Comparison between Parallel GA Based on Linkage Identification and Parallel Bayesian Optimization Algorithm", Proceedings of the International Conference on Cybernetics and Information Technol・・・

  2004 [Not refereed][Not invited]
   

  Naoya Murao, Masaharu Munetomo, Kiyoshi Akama: "Performance Comparison between Parallel GA Based on Linkage Identification and Parallel Bayesian Optimization Algorithm", Proceedings of the International Conference on Cybernetics and Information Technologies, Systems and Applications (CITSA2004), 3:136-141 (2004)*
• Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama: "Linkage Identification by Nonlinearity Check for Real-coded Genetic Algorithms", Genetic and Evolutionary Computation - GECCO2004 Part 2, Lecture Notes in Computer Science, 3103:222-233 (2004)*

  2004 [Not refereed][Not invited]
  
• Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama: "Modeling Dependencies of Loci with String Classification According to Fitness Differences", Genetic and Evolutionary Computation - GECCO2004 Part 2, Lecture Notes in Computer Science, 3103:246-257 (2004)*

  2004 [Not refereed][Not invited]
  
• Designing a Distributed Algorithm for Bandwidth Allocation with a Genetic Algorithm

  Hidehiro Kobayashi, Masaharu Munetomo, Kiyoshi Akama, Yoshiharu Sato

  Systems and Computers in Japan 35 (3) 37 - 45 0882-1666 2004 [Not refereed][Not invited]
   

  When stream communications which requires a certain bandwidth during a certain time is to be realized on an existing network, a bandwidth allocation algorithm that efficiently allocates network resources is crucial to satisfying user service requirements. In the optimization of allocation in a small-scale network, the most efficient approach is to have one node manage network information and perform allocation in a concentrated scheme. However, in bandwidth allocation the computation time required for optimization increases in proportion to the network scale, and distribution of the algorithm becomes necessary in the implementation. Another advantage of the distributed scheme is that allocations can be continued even if a fault arises in the network, which improves the fault tolerance of the algorithm. This paper investigates distribution of the bandwidth allocation algorithm by using a genetic algorithm. An improved algorithm is proposed which can cope with the fault when it occurs in the network by the reallocation of all communications. The proposed algorithm includes both local optimization to optimize the allocation at each node to reduce the computation time, and global optimization to optimize the whole network by the tournament method while performing local optimization in each node. Simulation experiments comparing the performance of the concentrated algorithm and the proposed algorithm are described. © 2004 Wiley Periodicals, Inc.
• Masaharu Munetomo: "Estimation of Distribution Algorithms without Explicit Selections", Proceedings of The 8th World Multi-Conference on Systemics, Cybernetics and Informatics (SCI2004), 5:80-85 (2004)

  2004 [Not refereed][Not invited]
  
• Estimation of distribution algorithms without explicit selections

  M Munetomo

  8TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL V, PROCEEDINGS 80 - 85 2004 [Refereed][Not invited]
   

  This paper proposes estimation of distribution algorithms without explicit selections by introducing assignment functions in their probabilistic model building process. Estimation of distribution algorithms build a probabilistic model from a selected population of promising solutions, which is employed to generate offsprings of the next generation. Instead employing selections, our model employs assignment functions which give relative weight of strings in a given population. By the assignment functions, we can improve quality of model building without performing explicit selections. Through numerical experiments, we show the effectiveness of the proposed methods compared with conventional EDA methods.
• Modeling dependencies of loci with string classification according to fitness differences

  M Tsuji, M Munetomo, K Akama

  GENETIC AND EVOLUTIONARY COMPUTATION GECCO 2004 , PT 2, PROCEEDINGS 3103 246 - 257 0302-9743 2004 [Refereed][Not invited]
   

  Genetic Algorithms perform crossovers effectively when we can identify a set of loci tightly linked to form a building block. Several methods have been proposed to detect such linkage. Linkage identification methods investigate fitness differences by perturbations of gene values and EDAs estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of loci by estimating the distribution of strings classified according to fitness differences. The proposed algorithm called the Dependency Detection for Distribution Derived from df (DDDDD or D-5) can detect dependencies of a problem which is difficult for EDAs requiring lower computation cost than linkage identifications.
• Empirical investigations on parallelized linkage indentification

  M Munetomo, N Murao, K Akama

  PARALLEL PROBLEM SOLVING FROM NATURE - PPSN VIII 3242 322 - 331 0302-9743 2004 [Refereed][Not invited]
   

  To solve GA-difficult problems in which we cannot ensure tight linkage in their encoding, advanced methods such as linkage identification techniques and estimation of distribution algorithms work effectively although they need some additional computational cost. The computation time can be reduced by employing parallel computers and several approaches have been proposed for their parallelized algorithms. This paper presents empirical results on parallelization of the linkage identification compared to that of an estimation of distribution algorithm.
• Performance comparison between parallel GA based on linkage identification and parallel Bayesian optimization algorithm

  N Murao, M Munetomo, K Akama

  ISAS/CITSA 2004: International Conference on Cybernetics and Information Technologies, Systems and Applications and 10th International Conference on Information Systems Analysis and Synthesis, Vol 3, Proceedings 136 - 141 2004 [Refereed][Not invited]
   

  Genetic Algorithms (GAs) are considered robust optimization algorithms which can solve wide-spectrum of difficult problems such as combinatorial optimization problems. Still, there are some GA-difficult problems which cannot ensure tight linkage in encoding strings. In such problems, crossovers cannot perform effectively on loosely encoded strings due to building block disruptions. Recently, a series of advanced techniques in evolutionary computations have been proposed to solve such GA-difficult problems. As one of these techniques, linkage identification checks nonlinearity caused by bit-wise perturbations for pairs of loci. Another advanced technique is Estimation of Distribution Algorithms (EDAs) which estimates probabilistic distribution for populations, and the Bayesian Optimization Algorithm (BOA) is the most sophisticated method in the EDAs. These methods can solve GA-difficult problem, paying additional computational cost. Therefore, parallel versions of these techniques, parallel GA based on linkage identification and parallel BOA, are studied to reduce computation time. In this paper, we compare performance of the parallel GA based on linkage identification with that of parallel BOA in actual parallel computing environment From the results, we consider relations between performance of the algorithms and the characteristics of the problems to be solved. Finally, we make discussions on the problem domains which algorithm performs more efficiently.
• Linkage identification by nonlinearity check for real-coded genetic algorithms

  M Tezuka, M Munetomo, K Akama

  GENETIC AND EVOLUTIONARY COMPUTATION GECCO 2004 , PT 2, PROCEEDINGS 3103 222 - 233 0302-9743 2004 [Refereed][Not invited]
   

  Linkage identification is a technique to recognize decomposable or quasi-decomposable sub-problems. Accurate linkage identification improves GA's search capability. We introduce a new linkage identification method for Real-Coded GAs called LINC-R (Linkage Identification by Nonlinearity Check for Real-Coded GAs). It tests nonlinearity by random perturbations on each locus in a real value domain. For the problem on which the proportion of nonlinear region in the domain is smaller, more perturbations are required to ensure LINC-R to detect nonlinearity successfully. If the proportion is known, the population size which ensures a certain success rate of LINC-R can be calculated. Computational experiments on benchmark problems showed that the CA with LINGR outperforms conventional Real-Coded CAs and those with linkage identification by a correlation model.
• Miwako Tsuji, Masaharu Munetomo, and Kiyoshi Akama: "Metropolitan Area Network Design Using GA Based on Hierarchical Linkage Identification", Genetic and Evolutionary Computation Part 2, Lecture Notes in Computer Science 2724:1616-1617 (2003)*

  2003 [Not refereed][Not invited]
  
• Masaharu Munetomo, Naoya Murao, and Kiyoshi Akama: "A Parallel Genetic Algorithm Based on Linkage Identification", Genetic and Evolutionary Computation Part 1, Lecture Notes in Computer Science 2723:1222-1233 (2003)*

  2003 [Not refereed][Not invited]
  
• Metropolitan area network design using GA based on Hierarchical linkage identification

  Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2724 1614 - 1615 1611-3349 2003 [Refereed][Not invited]
  
• Metropolitan area network design using GA based on hierarchical linkage identification

  M Tsuji, M Munetomo, K Akama

  GENETIC AND EVOLUTIONARY COMPUTATION - GECCO 2003, PT II, PROCEEDINGS 2724 1616 - 1617 0302-9743 2003 [Refereed][Not invited]
  
• A parallel genetic algorithm based on linkage identification

  M Munetomo, N Murao, K Akama

  GENETIC AND EVOLUTIONARY COMPUTATION - GECCO 2003, PT I, PROCEEDINGS 2723 1222 - 1233 0302-9743 2003 [Refereed][Not invited]
   

  Linkage identification algorithms identify linkage groups sets of loci tightly linked - before genetic optimizations for their recombination operators to work effectively and reliably. This paper proposes a parallel genetic algorithm (GA) based on the linkage identification algorithm and shows its effectiveness compared with other conventional parallel GAs such as master-slave and island models. This paper also discusses applicability of the parallel GAs that tries to answer "which method of the parallel GA should be employed to solve a problem?".
• Proposal of a Linkage Identification Method Based on Epistasis Measure

  MUNETOMO MASAHARU

  情報処理学会論文誌数理モデル化と応用（TOM） 一般社団法人情報処理学会 43 (10) 6 - 13 1882-7780 2002/11/15 [Not refereed][Not invited]
   

  Genetic Algorithms realize effective search by exchanging building blocks through genetic recombinations. To realize effective genetic search, linkage identification becomes important which detects a set of loci tightly linked to form a building block. Several methods are already proposed to identify linkage such as linkage learning algorithms based on probabilistic models and linkage identification procedures based on nonlinearity or non-monotonicity detection. In this paper, we extend the Linkage Identification by Nonlinearity Check (LINC) which identifies linkage based on nonlinearity detection by defining an epistasis measure for each pair of loci to realize linkage identification with the epistasis measure.
• Proposal of a Linkage Identification Method Based on Epistasis Measure(≤Special Issue≥Special Issue on Evolutionary Computation)

  MUNETOMO MASAHARU

  情報処理学会論文誌. 数理モデル化と応用 一般社団法人情報処理学会 43 (10) 6 - 13 0387-5806 2002/11/15 [Not refereed][Not invited]
   

  Genetic Algorithms realize effective search by exchanging building blocks through genetic recombinations. To realize effective genetic search, linkage identification becomes important which detects a set of loci tightly linked to form a building block. Several methods are already proposed to identify linkage such as linkage learning algorithms based on probabilistic models and linkage identification procedures based on nonlinearity or non-monotonicity detection. In this paper, we extend the Linkage Identification by Nonlinearity Check (LINC) which identifies linkage based on nonlinearity de...
• A Genetic Algorithm Using Linkage Identification for Metropolitan Area Network Design

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  情報処理学会論文誌数理モデル化と応用（TOM） 一般社団法人情報処理学会 43 (7) 80 - 91 1882-7780 2002/09/15 [Not refereed][Not invited]
   

  In genetic algorithms, it is important to encode strings ensuring tight linkage for their building blocks. In network design problems, however, it is difficult to encode strings appropriately because network design is dependent not only on geographical constraints but also on other complex factors such as bias on traffic demands, routing policy, and so on. Although there's many applications of genetic algorithms to network topology design, most of them haven't paid attention to tight encoding of building blocks, or considered only geographical characteristics. In order to realize tight linkage among loci and realize effective genetic search, this paper introduces LIEM (Linkage Identification with Epistasis Measure) - a technique for identifying linkage sets, sets of loci tightly liked to form building blocks - to realize effective network design. Through empirical studies, we show the effectiveness of the network design with the LIEM compared to that with conventional genetic algorithms.
• A Genetic Algorithm Using Linkage Identification for Metropolitan Area Network Design

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI

  情報処理学会論文誌. 数理モデル化と応用 一般社団法人情報処理学会 43 (7) 80 - 91 0387-5806 2002/09/15 [Not refereed][Not invited]
   

  In genetic algorithms, it is important to encode strings ensuring tight linkage for their building blocks. In network design problems, however, it is difficult to encode strings appropriately because network design is dependent not only on geographical constraints but also on other complex factors such as bias on traffic demands, routing policy, and so on. Although there's many applications of genetic algorithms to network topology design, most of them haven't paid attention to tight encoding of building blocks, or considered only geographical characteristics. In order to realize tight link...
• Load Balancing Routing with Genetic Algorithm Based on Link Load Metric

  YAMAGUCHI Naohiko, MUNETOMO Masaharu, AKAMA Kiyoshi, SATO Yoshiharu

  Transactions of Information Processing Society of Japan 一般社団法人情報処理学会 43 (7) 2359 - 2367 1882-7764 2002/07/15 [Not refereed][Not invited]
   

  In packet switching networks such as the Internet, to utilize network resources effectively, routing algorithms with genetic algorithms have been proposed which generate alternative routes by genetic operators to balance loads among them and prevent congestions. This paper proposes adaptive genetic operators based on link load metric for the genetic routing algorithms in order to realize rapid evaluations of network load status and effective generations of alternative routes. Through simulation experiments performed on a network simulator, we show the effectiveness of the proposed method.
• Load Balancing Routing with Genetic Algorithm Based on Link Load Metric

  YAMAGUCHI NAOHIKO, MUNETOMO MASAHARU, AKAMA KIYOSHI, SATO YOSHIHARU

  IPSJ Journal 一般社団法人情報処理学会 43 (7) 2359 - 2367 0387-5806 2002/07/15 [Not refereed][Not invited]
   

  In packet switching networks such as the Internet, to utilize network resources effectively, routing algorithms with genetic algorithms have been proposed which generate alternative routes by genetic operators to balance loads among them and prevent congestions. This paper proposes adaptive genetic operators based on link load metric for the genetic routing algorithms in order to realize rapid evaluations of network load status and effective generations of alternative routes. Through simulation experiments performed on a network simulator, we show the effectiveness of the proposed method.
• Designing a Distributed Algorithm for Bandwidth Allocation with Genetic Algorithms

  KOBAYASHI Hidehiro, MUNETOMO Masaharu, AKAMA Kiyoshi, SATO Yoshiharu

  The Transactions of the Institute of Electronics,Information and Communication Engineers. 一般社団法人電子情報通信学会 85 (5) 445 - 452 0915-1915 2002/05/01 [Not refereed][Not invited]
   

  既存のネットワーク上で一定時間,一定の帯域幅を必要とするストリーム通信を実現する場合,ユーザからのサービス要求を満たすにはネットワーク資源を効率的に配分する帯域幅割当てアルゴリズムが重要となる.小規模なネットワークにおける割当ての最適化は,あるノードがネットワーク情報を集中的に管理し一括した割当てを実行する方法が最も効率が良い.しかし,帯域幅割当てはネットワーク規模の増加に比例して最適化に必要とする計算時間が増加するため,実装を考慮した場合にはアルゴリズムの分散化が必要となる.また分散化することによりネットワーク障害が発生した場合でも割当てが可能となり,アルゴリズムの耐障害性が向上する.本論文では,既存の遺伝的アルゴリズムによる帯域幅割当てアルゴリズムの分散化を目的とし,同時にネットワーク障害が発生した場合に全通信の再割当てを行うことで障害への対応を実現した改良アルゴリズムを提案する.本アルゴリズムの特徴は,計算時間を軽減するために各ノードで割当ての最適化を実行する局所的最適化と,全ノードで局所的最適化を実行しながら勝ち抜き戦を行うことでネットワーク全体を最適化する大域的最適化とを組み合わせて構成していることである.更にシミュレーション実験を行うことで,集中型アルゴリズムと提案アルゴリズムの性能について検討する.
• 「遺伝的アルゴリズムによる帯域幅割当てのための分散アルゴリズムの設計」

  『電子情報通信学会論文誌 D-I』 J85-D-I (5) 445 - 452 2002 [Not refereed][Not invited]
  
• Yuichi Yamamoto, Takahiko Ishikawa, Kiyoshi Akama, Masaharu Munetomo: "A Foundation for Algorithm Generation by Transforming Meta-descriptions", Proceedings of the 2002 International Conference on Fuzzy Systems and Knowledge Discovery, 12-716 (2002)*

  2002 [Not refereed][Not invited]
  
• Masaharu Munetomo, Miwako Tsuji, Kiyoshi Akama: "Metropolitan Area Network Design Using GA Based on Linkage Identification with Epistasis Measures", Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning, 652-656 (2002)*

  2002 [Not refereed][Not invited]
  
• Masaharu Munetomo: "Linkage Identification with Epistasis Measure Considering Monotonicity Conditions", Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning, 550-554 (2002)*

  2002 [Not refereed][Not invited]
  
• Masaharu Munetomo: "Linkage Identification Based on Epistasis Measures to Realize Efficient Genetic Algorithms", Proceedings of the 2002 Congress on Evolutionary Computation, 1332-1337 (2002)*

  2002 [Not refereed][Not invited]
  
• Linkage identification based on epistasis measures to realize efficient genetic algorithms

  M Munetomo

  CEC'02: PROCEEDINGS OF THE 2002 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1 AND 2 1332 - 1337 2002 [Refereed][Not invited]
   

  Genetic algorithms (GAs) process building blocks (BBs) mixed and tested through genetic recombination operators. To realize effective BB processing, linkage identification is essential which detects a set of loci tightly linked. This paper proposes a linkage identification with epistasis measures (LIEM) that detects linkage groups based on a pair-wise epistasis measure.
• Masaharu Munetomo: The Genetic Adaptive Routing Algorithm, in Telecommunications Optimisation: Heuristic and Adaptive Methods, pp.151-166, John Weily & Sons*

  2001 [Not refereed][Not invited]
  
• Hidehiro Kobayashi, Masaharu Munetomo, Kiyoshi Akama, and Yoshiharu Sato: A Distributed Algorithm for Bandwidth Allocation in Multimedia Networks, Proceedings of the 5th International Conference on Artificial Evolution, 251-262 (2001)*

  2001 [Not refereed][Not invited]
  
• Masaharu Munetomo, Naohiko Yamaguchi, Kiyoshi Akama, and Yoshiharu Sato: Empirical Investigations oon the Genetic Adaptive Routing Algorithm in the Internet, Proceedings of the Congress on Evolutionary Computation 2001, 1236-1243 (2001)*

  2001 [Not refereed][Not invited]
  
• Masaharu Munetomo: The Genetic Adaptive Routing Algorithm, in Telecommunications Optimisation: Heuristic and Adaptive Methods, pp.151-166, John Weily & Sons*

  2001 [Not refereed][Not invited]
  
• Empirical investigations on the genetic adaptive routing algorithm in the Internet

  M Munetomo, N Yamaguchi, K Akama, Y Sato

  PROCEEDINGS OF THE 2001 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1 AND 2 1236 - 1243 2001 [Refereed][Not invited]
   

  This paper discusses improvement of genetic operators and fitness evaluation policies of the genetic adaptive routing algorithm we have proposed elsewhere. First, we introduce a threshold policy in evaluating link load status that is commonly employed in dynamic load balancing algorithms. Second. we discuss policies to trigger link load status observations to evaluate fitness values. Third, we introduce adaptive path mutation and path crossover operators to enhance their ability to generate well-performed alternative routes. Through empirical studies, we investigate optimal way for the load status observations and validate the effectiveness of the adaptive genetic operators.
• Masaharu Munetomo: The Genetic Adaptive Routing Algorithm, in Telecommunications Optimisation: Heuristic and Adaptive Methods, pp.151-166, John Weily & Sons (2000). *

  2000 [Not refereed][Not invited]
  
• Masaharu Munetomo: Network Routing with the Use of Evolutionary Methods, in Computational Intelligence in Telecommunication Networks (分担 : Witold Pedrycz and Athanasios V. Vasilakos, editors), CRC Press (2000).

  2000 [Not refereed][Not invited]
  
• Masaharu Munetomo, David E. Goldberg: Linkage Identification by Non-monotonicity Detection for Overlapping functions, Evolutionary Computation, vol.7, No.4, pp.377-398*

  1999 [Not refereed][Not invited]
  
• Masaharu Munetomo, David E. Goldberg: A Genetic Algorithm Using Linkage Identification by Nonlinearity Check, Proceedings of the 1999 IEEE Conference on System, Man, and Cybernetics (1999)

  1999 [Not refereed][Not invited]
  
• Masaharu Munetomo, David E. Goldberg: Identifying Linkage Groups by Nonlinearity/Non-monotonicity Detection, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pp.433-440 (1999)

  1999 [Not refereed][Not invited]
  
• Masaharu Munetomo, David E. Goldberg: Linkage Identification by Non-monotonicity Detection for Overlapping functions, Evolutionary Computation, vol.7, No.4, pp.377-398 (1999)

  1999 [Not refereed][Not invited]
  
• Linkage Identification by Non-monotonicity Detection for Overlapping Functions

  Munetomo Masaharu, Goldberg David E

  Evolutionary Computation MIT Press 7 (4) 377 - 398 1063-6560 1999 [Not refereed][Not invited]
   

  This paper presents the linkage identification by non-monotonicity detection (LIMD) procedure and its extension for overlapping functions by introducing the tightness detection (TD) procedure. The LIMD identifies linkage groups directly by performing order-2 simultaneous perturbations on a pair of loci to detect monotonicity/non-monotonicity of fitness changes. The LIMD can identify linkage groups with at most order of k when it is applied to O(2k) strings. The TD procedure calculates tightness of linkage between a pair of loci based on the linkage groups obtained by the LIMD. By removing l...
• A Migration Scheme of the Genetic Adaptive Routing Algorithm

  Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato

  Proc. of IEEE Int. Conf. on Systems, Man and Cybernetics, 2774 - 2779 1998/07 [Refereed][Not invited]
  
• An Adaptive Routing Algorithm with Load Balancing by a Genetic Algorithm

  MUNEASA Masaharu, TAKAI Yoshiaki, SATO Yoshiharu

  Transactions of Information Processing Society of Japan 一般社団法人情報処理学会 39 (2) 219 - 227 1882-7764 1998/02/15 [Not refereed][Not invited]
   

  This paper presents an adaptive routing algorithm which has a load balancing mechanism among alternative paths by a genetic algorithm. Conventional routing algorithms such as RIP and SPF broadcast information on routing tables or link status in a network, which yields much communication overhead and degrades total performance when the network becomes large. Conventional routing algorithms only generate the shortest path to send a packet, even if some good alternative paths are available. Our routing algorithm generates alternative paths and observes communication latency only for paths frequently used. This mechanism greatly reduces communication cost for information exchangind of the routing. Moreover this algorithm realizes load balancing on the alternative paths by distributing packets among them. We perform simulation experiments using a discrete event simulator of network communication. The result of the experiments shows that our algorithm achieves effective routing with less communication overhead.
• An Adaptive Routing Algorithm with Load Balancing by a Genetic Algorithm (Multimedia・Distirbuted and Cooperative Computing)

  MUNETOMO MASAHARU, TAKAI YOSHIAKI, SATO YOSHIHARU

  IPSJ Journal 一般社団法人情報処理学会 39 (2) 219 - 227 0387-5806 1998/02/15 [Not refereed][Not invited]
   

  This paper presents an adaptive routing algorithm which has a load balancing mechanism among alternative paths by a genetic algorithm. Conventional routing algorithms such as RIP and SPF broadcast information on routing tables or link status in a network, which yields much communication overhead and degrades total performance when the network becomes large. Conventional routing algorithms only generate the shortest path to send a packet, even if some good alternative paths are available. Our routing algorithm generates alternative paths and observes communication latency only for paths freq...
• 遺伝的アルゴリズムによる負荷分散機構を有する適応型ルーティング

  情報処理学会論文誌 Vol.38 (No.2) 219 - 227 1998 [Not refereed][Not invited]
  
• Shuichi Moriguti, Masaharu Munetomo, Yoshiharu Sato: A Moving Average Method for Predicting Process Resource Usage Based on a State Transition Model, Proceedings of the 1998 Conference of the North American Fuzzy Information Processing Society, pp.82-85*

  1998 [Not refereed][Not invited]
  
• Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato: A Migration Scheme for the Genetic Adaptive Routing Algorithm, Proceedings of the 1998 IEEE Conference on Systems, Man, and Cybernetics, pp.2774-2779*

  1998 [Not refereed][Not invited]
  
• Shuichi Moriguti,Masaharu Munetomo,Yoshiharu Sato:A Moving Average Method for Predicting Process Resource Usage Based on a State Transition Model(North American Fuzzy Information Processing Society(NAFIPS'98),1998)

  1998 [Not refereed][Not invited]
  
• Masaharu Munetomo,Yoshiaki Takai,Yoshiharu Sato:A Migration Scheme for the Genetic Adaptive Routing Algorithm (IEEE Conference on Systems,Man,and Cybernetics(SMC'98),1998)

  1998 [Not refereed][Not invited]
  
• A moving average method for predicting process resource usage based on a state transition model

  S Moriguchi, M Munetomo, Y Sato

  1998 CONFERENCE OF THE NORTH AMERICAN FUZZY INFORMATION PROCESSING SOCIETY - NAFIPS 82 - 85 1998 [Refereed][Not invited]
   

  In this paper, we develop a prediction algorithm for process resource usage based on a state-transition model, The state transition model is built by using a k-means clustering algorithm. applied to a series of 2-dimensional observed parameters on process resource usage such as Load average and Free memory in computer. Our prediction algorithm. estimates the parameters from state transition probabilities of the model. To reduce prediction error, we introduce a moving average method in the prediction algorithm..
• An Intelligent Network Routing Algorithm by a Genetic Algorithm

  Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato

  Proc. of the 4th Int. Conf. on Neural Information Processing 1 547 - 550 1997/11 [Refereed][Not invited]
  
• An Adaptive Network Routing Algorithm Employing Path Genetic Operators

  Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato

  Proc. of the 7th Int. Conf. on Genetic Algorithms 643 - 649 1997/07 [Refereed][Not invited]
  
• An Application of a Stochastic Algorithmo to Invisible Matrices Games

  TOMIKAWA Yuuki, MUNETOMO Masaharu, TAKAI Yoshiaki

  The Transactions of the Institute of Electronics,Information and Communication Engineers. 一般社団法人電子情報通信学会 80 (2) 700 - 702 0915-1923 1997/02/25 [Not refereed][Not invited]
   

  強化学習機構を有する遺伝的アルゴリズム (StGA) [1], 利得行列の内容が不可視であり, 可能な行動の数が多いゲームヘ適用する. StGAのもととなった確率学習オートマトンとの比較実験を通し, こうしたゲームに対するStGA適用の有効性を検証する.
• 「利得行列が不可視である行列ゲームへのStGAの適用」

  『電子情報通信学会論文誌』 J80-D-II (2) 700 - 702 1997 [Not refereed][Not invited]
  
• Munetomo, M., Takai, Y. and Sato, Y. : "An Adaptive Network Routing Algorithm Employing Path Genetic Operators", Proceedings of the Seventh International Conference on Genetic Algorithms, 643-649 (1997)＊

  1997 [Not refereed][Not invited]
  
• Munetomo, M., Takai, Y. and Sato, Y. : "An Intelligent Network Routing Algorithm by a Genetic Algorithm", Proceedings of the 1997 International Conference on Neural Information Processing and Intelligent Information Systems, 547-550 (1997)＊

  1997 [Not refereed][Not invited]
  
• Munetomo, M., Takai, Y. and Sato, Y. : "StGA : An Application of a Genetic Algorithm to Stochastic Learning Automata", Systems and Computers in Japan, 27(10) : 68-78 (1997)＊

  1997 [Not refereed][Not invited]
  
• StGA : An Application of a Genetic Algorithm to Stochastic Learning Automata

  Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato

  Systems and Computers in Japan 27 (10) 68 - 78 1996/10 [Refereed][Not invited]
  
• Masaharu Munetomo, Yoshiaki Takai, and Yoshiharu Sato: "Genetic-Based Dynamic Load Balancing: Implementation and Evaluation", Parallel Problem Solving from Nature, Lecture Notes in Computer Science 1141, 920--929 (1996)*

  1996 [Not refereed][Not invited]
  
• Masaharu Munetomo, Yoshiaki Takai, and Yoshiharu Sato: "StGA: An application of a Genetic Algorithm to Stochastic Learning Automata", Systems and Computers in Japan, Vol.27, No.10, 68-78. (1996)*

  1996 [Not refereed][Not invited]
  
• 「確率学習における遺伝的アルゴリズムの適用」

  『電子情報通信学会論文誌』 J79-D-II (2) 230 - 238 1996 [Not refereed][Not invited]
  
• On tracking-ability of a stochastic genetic algorithm to changing environments

  M Munetomo, Y Takai, Y Sato

  INFORMATION INTELLIGENCE AND SYSTEMS, VOLS 1-4 522 - 526 1996 [Refereed][Not invited]
   

  A stochastic genetic algorithm(StGA) effectively searches an optimal action which maximizes the probability to have reward payoffs in stochastic environments by employing stochastic learning automata and genetic algorithms. This paper discusses tracking-ability of the StGA to environmental changes from theoretical and empirical points of view. In the theoretical investigation, we employ an inhomogeneous Markov chain to formulate state transition of the probability for a population of actions to have an optimal one. We perform theoretical investigations on change of the probability to create an optimal action and of the probability to lose all the optimal ones. Simulation experiments are performed to show the effectiveness of the StGA in changing environments whose penalty probability vectors gradually or suddenly change.
• Genetic-based dynamic load balancing: Implementation and evaluation

  Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1141 920 - 929 1611-3349 1996 [Refereed][Not invited]
   

  This paper presents an adaptive dynamic load balancing scheme employing a genetic algorithm which includes an evaluation mechanism of fitness values in stochastic environments. A sender-initiative task migration algorithm continues to send unnecessary requests for a task migration while the system load is heavy, which brings much overhead before the migration finishes. In a genetic-based dynamic load balancing scheme we propose, a small subset of computers to which the requests are sent off is adaptively determined by a learning procedure to reduce unnecessary requests. The learning procedure consists of stochastic learning automata and genetic operators applied to a population of strings each of which stands for a subset of computers to which task migration requests are sent off. We implement the proposed algorithm on an actual distributed system which consists of UNIX workstations. We show the effectiveness of our approach through empirical investigations on the distributed system.
• A Dynamic Ｌoad Balancing Scheme Using a Genetic Algorithm with Stochastic Learning

  MUNETOMO Masaharu, TAKAI Yoshiaki, SATO Yoshiharu

  IPSJ Journal 一般社団法人情報処理学会 36 (4) 868 - 878 1882-7764 1995/04/15 [Not refereed][Not invited]
   

  It is necessary to balance the load of each processor in a distributed system in order to utilize the system effectively. In a dynamic load balancing algorithm with distributed control, each processor observes load status of the system and dispatches tasks independently. We propose a dynamic load balancing scheme with distributed control which employs stochastic multicast messages. We encode a sending set of the requests for task dispatch into a binary string to which genetic operations with stochastic learning are applied in order to increase the probability for the requests to be accepted. Through simulation studies, we compared our scheme with some conventional load balancing methods. The results show the effectiveness of our scheme concerning mean response time of the tasks, success rate of the requests, and adaptability to environmental changes.
• A Dynamic Load Balancing Scheme Using a Genetic Algorithm with Stochastic Learning

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu

  IPSJ Journal 一般社団法人情報処理学会 36 (4) 868 - 878 0387-5806 1995/04/15 [Not refereed][Not invited]
   

  It is necessary to balance the load of each processor in a distributed system in order to utilize the system effectively. In a dynamic load balancing algorithm with distributed control, each processor observes load status of the system and dispatches tasks independently. We propose a dynamic load balancing scheme with distributed control which employs stochastic multicast messages. We encode a sending set of the requests for task dispatch into a binary string to which genetic operations with stochastic learning are applied in order to increase the probability for the requests to be accepted...
• A stochastic genetic algorithm for dynamic load balancing in distributed systems

  M MUNETOMO, Y TAKAI, Y SATO

  1995 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS, VOLS 1-5 4 3795 - 3799 1995 [Refereed][Not invited]
  
• An Efficient String Exchange Algorithm for a Subpopulation - Based Asynchronously Parallel Genetic Algorithm and Its Evaluation

  MUNETOMO MASAHARU, TAKAI YOSHIAKI, SATO YOSHIHARU

  IPSJ Journal 一般社団法人情報処理学会 35 (9) 1815 - 1827 1882-7764 1994/09/15 [Not refereed][Not invited]
   

  We Present an efficient string exchange scheme on subpopulaiton-based parallel genetic algorithms. The subpopulation-based parallel genetic algorithm divides a population into subpopulations in which genetic operations are executed simultaneously. In this scheme, exchanging strings between subpopulations through communicating network is essential to avoiding performance degradation of genetic search due to uniformity of the subpopulation. To reduce unnecessary inter-processor communications is an important issue to realize efficient parallel computation. In conventional subpopulation-based parallel genetic algorithms, however, inefficient parallel computations are taken place because string exchanges are executed at a constant interval or fully at random. The sigma-exchange algorithm we propose observes a fitness distribution of each subpopulation and starts on exchanging strings only when the standard deviation of the fitness distribution of some subpopulation decreases to some ratio. The purpose of our algorithm is to obtain more precise solutions with less inter-processor communications. We show the effectiveness of our scheme through simulation experiments on a multicomputer network in which communications are realized via asynchronous message passing.
• A Genetic Approach to Dynamic Load Balancing in a Distributed Computing System

  MUNETOMO M.

  Proceedings of the First IEEE Conference on Evolutionary Computation 1 418 - 421 1994/06 [Refereed][Not invited]
  
• AN EFFICIENT MIGRATION SCHEME FOR SUBPOPULATION-BASED ASYNCHRONOUSLY PARALLEL GENETIC ALGORITHMS

  M MUNETOMO, Y TAKAI, Y SATO

  PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS 649 - 649 1993 [Refereed][Not invited]
  

Books etc

• アカデミッククラウド調査報告書2012 (新産業調査レポートシリーズ)

  吉岡 信和, 棟朝 雅晴, 本橋 賢二, 西村 一彦, 谷沢 智史, 横山 重俊 (Joint work)
  インプレスR&D 2012/08 210
• Advances in Grid Computing

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama (Contributorpp.19-28)
  2011
• Genetic algorithms - theory and advanced methods

  Masaharu Munetomo (Single work)
  森北出版 2008/07 (ISBN: 4627847815) 160

  
• Advances in Evolutionary Algorithms

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama (Contributorpp.315-334)
  IN-TECH 2008
• Linkage in Evolutionary Computation

  Asim Munawar, Mohamed Wahib, Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama (Contributorpp.159-187, pp.441-459)
  Springer 2008
• Computational Intelligence Paradigms – Innovative Applications

  Miwako Tsuji, Masaharu Munetomo (Contributorpp.251-280)
  Springer 2008
• 統計データ科学事典

  棟朝雅晴 (Contributor遺伝的アルゴリズム)
  2007
• Evolutionary Computation in Dynamic and Uncertain Environments

  Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama (Contributorpp.417-436)
  2007
• 遺伝的アルゴリズム4

  棟朝雅晴 (Contributor第９章：遺伝的アルゴリズムによる適応ルーティング)
  産業図書 2000 (ISBN: 4782851499)
• Telecommunications Optimisation: Heuristic and Adaptive Methods

  Masaharu Munetomo (Contributorpp.151-166)
  John Weily & Sons 2000
• Computational Intelligence in Telecommunication Networks

  Masaharu Munetomo (Contributorpp.287-302)
  CRC Press 2000

Conference Activities & Talks

• Optimal Feature Selection for Intrusion Detection Systems Employing Multi-Objective Genetic Algorithm  [Not invited]

  Chang Geng, Masaharu Munetomo

  2018 JPNSEC International Workshop on Evolutionary Computation  2018/08
• クラウドコンピューティングを用いた進化型ロボティックスワームの群れ行動生成  [Not invited]

  森川達矢, 保田俊行, 大倉和博, 松村嘉之, 棟朝雅晴

  計測自動制御学会システムインテグレーション部門講演会(CD-ROM)  2015/12
• インタークラウド環境下での大規模分散設計最適化のための最適化実行基盤の設計と実装  [Not invited]

  阿部友哉, 棟朝雅晴

  計測自動制御学会システム・情報部門学術講演会講演論文集(CD-ROM)  2015/11
• 設計者の要求に基づく非劣解分析支援システムの提案  [Not invited]

  中野翔, 渡邉真也, 千葉一永, 金崎雅博, 棟朝雅晴

  計測自動制御学会システム・情報部門学術講演会講演論文集(CD-ROM)  2015/11
• インタークラウド環境における仮想システム構築の最適化サービスに関する検討  [Not invited]

  玉家武博, 斎藤篤志, 三浦克宜, 棟朝雅晴

  情報処理学会全国大会講演論文集  2015/03
• 有翼式宇宙往還機の安定性を考慮した亜音速飛行時の空力設計  [Not invited]

  倉田優太, 金崎雅博, 千葉一永, 渡邉慎也, 棟朝雅晴

  数値流体力学シンポジウム講演論文集(CD-ROM)  2015
• 分散クラウドシステムにおける遠隔連携技術  [Invited]

  棟朝 雅晴

  学際大規模情報基盤共同利用・共同研究拠点 第1回ネットワーク型学際研究シンポジウム  2014/03
• インターネット上のデータ利活用を促進するための人間ベース遺伝的アルゴリズム  [Not invited]

  幸田里奈, 長谷部良輔, 大西圭, 棟朝雅晴

  第6回進化計算学会研究会  2014/03
• アカデミッククラウドにおけるCloudStackの活用事例と今後の展望  [Invited]

  棟朝 雅晴

  CloudStack Day Japan 2014  2014/03
• 研究支援に係るアカデミッククラウドの調査検討  [Not invited]

  棟朝 雅晴

  平成25年度国家課題対応型研究開発推進事業『アカデミッククラウド環境構築に係るシステム研究』提案「コミュニティで紡ぐ次世代大学ICT環境としてのアカデミッククラウド」最終報告会  2014/02
• 研究支援に係るアカデミッククラウド  [Not invited]

  棟朝 雅晴

  大学ICT推進協議会年次大会「コミュニティで紡ぐ次世代大学ICT環境としてのアカデミッククラウド」事業中間報告  2013/12
• 研究支援のためのアカデミッククラウド  [Not invited]

  棟朝 雅晴

  アカデミッククラウドシンポジウム2013  2013/09
• 単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによる宇宙探査機の多重重力支援軌道最適化  [Not invited]

  田中一真, 棟朝雅晴, 赤間清

  全国大会講演論文集  2013/03 

  複数天体の重力支援を利用した宇宙探査機の軌道最適化は,厳密解の発見が困難な,制約付き非線形多変数関数の最適化問題である.本研究では,欧州宇宙機関で公開されている軌道最適化問題を単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによって解く.
• Hadoop環境上で動作する研究分野判定ツールの試作  [Not invited]

  平島慶典, 三浦克宜, 棟朝雅晴

  全国大会講演論文集  2013/03 

  本研究では、与えられた論文に対して、的確な研究分野を判定するためのツールを開発する。研究を発展させる上で、関連研究のサーベイは重要であり、そのためには論文の適切な研究分野を知ることは極めて大切である。適切な研究分野を発見する方法として過去の論文と照らし合わせる方法が考えられる。しかしそれには膨大な計算量が掛かるため、逐次処理ではコストがかかる。この問題を解決するために、並列計算を使用している。研究分野の位置づけを行うために、本論文ではMahoutによるクラスタリングを行っており、そのための計算は、Hadoopを利用した並列計算を使用している。
• クラウドコンピューティングの最新動向  [Invited]

  棟朝 雅晴

  OR学会北海道支部講演会  2013/02
• 北海道大学アカデミッククラウドの活用事例  [Invited]

  棟朝 雅晴

  学術情報基盤オープンフォーラム「大学クラウド活用における、検証と課題と対策」  2013/02
• 北海道大学アカデミッククラウドのご紹介とクラウド技術の最新動向，研究動向について  [Invited]

  棟朝 雅晴

  第2回デバイスとクラウドの高度融合による新事業創出研究会  2013/01
• リンケージツリー遺伝的アルゴリズムにおける計算量削減の検討  [Not invited]

  鈴木一史, 棟朝雅晴

  進化計算シンポジウム2012講演論文集  2012/12
• スワームロボットシステムにおける大規模並列計算環境を用いた分散型CMA-ESの実装  [Not invited]

  竹中貴治, 保田俊行, 大倉和博, 松村嘉之, 棟朝雅晴

  進化計算シンポジウム2012講演論文集  2012/12
• クラウド環境における進化計算用グリッドサービスの並列化効率の評価  [Not invited]

  藤田二夫, 保田俊行, 大倉和博, 松村嘉之, 伍賀正典, 棟朝雅晴

  進化計算シンポジウム2012講演論文集  2012/12
• 異なるクラウド管理ソフトウェア環境の相互接続方式に関する検討  [Not invited]

  相澤孝至, 棟朝雅晴

  情報処理北海道シンポジウム講演論文集  2012/10
• ASNARO‐RCMを用いたOCTA/cognacのパラメータサーベイの効率化に関する報告  [Not invited]

  萩田克美, 棟朝雅晴, 上島豊, 大宮学

  計算工学講演会論文集(CD−ROM)  2012/05
• Hokkaido University Academic Cloud: Largest Academic Cloud System in Japan  [Invited]

  Masaharu Munetomo

  Cloud Technical Leadership Forum  2012/05
• Report of a study for efficient multi-parameter survey of OCTA/cognac using ASNARO-RCM  [Not invited]

  萩田 克美, 棟朝 雅晴, 上島 豊

  計算工学講演会論文集 Proceedings of the Conference on Computational Engineering and Science  2012/05
• 北海道大学アカデミッククラウドの構築とサービスについて  [Invited]

  棟朝雅晴

  アカデミッククラウドワークショップ2012＠広島  2012/02
• 北海道大学における大規模学術クラウドの構築と運用について  [Invited]

  棟朝雅晴

  サイエンティフィック研究会システム技術分科会第２回会合  2012/01
• 北海道大学アカデミッククラウドの構築と運用について  [Invited]

  棟朝雅晴

  グリッド協議会第33回ワークショップ  2011/12
• 北海道大学アカデミッククラウド〜国内最大規模の学術クラウドについて  [Invited]

  棟朝雅晴

  Open Cloud Conference 2011 in Sapporo  2011/12
• Estimation of Distribution Algorithms without Explicit Selections  [Invited]

  Masaharu Munetomo

  The 8th World Multi-Conference on Systemics, Cybernetics and Informatics  2004
• Linkage Identification by Non-monotonicity Detection for Overlapping Functions  [Invited]

  Masaharu Munetomo

  Journal Showcase at the 2000 Genetic and Evolutionary Computation Conference  2000
• Designing Genetic Algorithms for Adaptive Routing Algorithms in the Internet  [Invited]

  Masaharu Munetomo

  Workshop on Evolutionary telecommunications: Past, present, and future, at the 1999 Genetic and Evolutionary Computation Conference  1999

MISC

• Generating Collective Behavior of a Multi-Legged Robotic Swarm with Neuroevolution : A Case Study in a Two-landmark Navigation Problem

  塚本遙日, 森本大智, 平賀元彰, 大倉和博, 棟朝雅晴  システム制御情報学会研究発表講演会講演論文集(CD-ROM)  65-  851  -858  2021/05/26
• 「情報処理学会論文誌：数理モデル化と応用」の編集にあたって

  棟朝 雅晴  情報処理学会論文誌数理モデル化と応用（TOM）  14-  (1)  i  -i  2021/01/27
• Introducing modular networks based on multi-objective neuroevolution in rogue-like game

  高橋寿徳, 棟朝雅晴  情報処理学会研究報告(Web)  2021-  (MPS-132)  2021
• Design of a model for estimating the difficulty of holds in sport climbing

  西野直登, 桂大地, 棟朝雅晴, 棟朝雅晴  情報処理学会研究報告(Web)  2021-  (MPS-132)  2021
• 「情報処理学会論文誌：数理モデル化と応用」の編集にあたって

  棟朝 雅晴  情報処理学会論文誌数理モデル化と応用（TOM）  13-  (2)  i  -i  2020/08/28
• Distribution System for Japanese Synthetic Population Data with Protection Level

  Murata Tadahiko, Ichikawa Manabu, Goto Yusuke, Sugiki Akiyoshi, Date Susumu, Hanawa Toshihiro, Harada Takuya, Munetomo Masaharu, Hao Lee  Proceedings of the Fuzzy System Symposium  36-  (0)  269  -272  2020  

  In this paper, we introduce a distribution system of synthesized data of Japanese population using Interdisciplinary Large-scale Information Infrastructures in Japan. Synthesized population is synthesized based on the statistics of census that are publicly released. Therefore, the synthesized data have no privacy data. However, since it is easy to estimate the compositions of households, working status in a certain area from the synthesized population, we distribute the synthesized data only for public or academic purposes. In the academic purposes, it is important to encourage young scholars to use a large-scale data of households, we define security levels for the attributes in the synthesized populations. According to the security levels, we distribute the data with proper attributes to applicants. We encourage researchers to use the synthetic populations to be familiar to large-scale data processing.

• Generating Collective Behavior of Multi-legged Robotic Swarm with Deep Neuroevolution

  MORIMOTO Daichi, HIRAGA Motoaki, OHKURA Kazuhiro, MATSUMURA Yoshiyuki, MUNETOMO Masaharu  Proceedings of the Annual Conference of JSAI  2020-  (0)  2M5OS3b02  -2M5OS3b02  2020  

  In this paper, the controller of the multi-legged robotic swarm is designed by deep neuroevolution, which is a technique to train a deep neural network by using artificial evolution. The computer simulations are conducted with a 3D physics engine called Bullet. An aggregation task is examined with varying the sensor range to discuss the behavior. The results show that deep neuroevolution was able to generate collective behavior of the multi-legged robotic swarm. Moreover, the robotic swarm showed a potential behavior that might be useful to achieve more complex tasks.

• 「情報処理学会論文誌：数理モデル化と応用」の編集にあたって

  棟朝 雅晴  情報処理学会論文誌数理モデル化と応用（TOM）  12-  (3)  i  -i  2019/12/23
• 北海道大学ハイパフォーマンスインタークラウドの設計,構築,運用まで (特集 総合力で造る情報基盤)

  杉木 章義, 棟朝 雅晴  オペレーションズ・リサーチ = Communications of the Operations Research Society of Japan : 経営の科学  64-  (9)  507  -513  2019/09
• エッジコンピューティング環境における広域分散アプリケーションの多目的最適資源割当

  藤田駿一, 棟朝雅晴  情報処理学会研究報告(Web)  2019-  (CSEC-84)  Vol.2019‐CSEC‐84,No.13,1‐6 (WEB ONLY)  2019/02/25  [Not refereed][Not invited]
  
• Introducing Modular Neural Networks in Learning Action Games

  TAKAHASHI Toshinori, MUNETOMO Masaharu  Proceedings of the Annual Conference of JSAI  2019-  (0)  4Rin140  -4Rin140  2019  [Not refereed][Not invited]
   

  In this paper, we introduce a modular network approach in neuroevolution for action game learning. We employ NEAT (NeuroEvolution of Augmenting Topologies) to generate modular networks learning game stages under different conditions, which are combined to obtain networks that can adapt to difficult situations appeared in actual game playing. We show the effectiveness of our approach in a Pygame instance compared to the original NEAT.

• クラウドとエッジサーバを用いた広域分散アプリケーションの最適資源割り当てに関する検討

  藤田駿一, 棟朝雅晴  情報科学技術フォーラム講演論文集  17th-  103‐106  2018/09/12  [Not refereed][Not invited]
  
• 実数値多目的最適化問題におけるリンケージ同定手法の性能検証

  泉谷光祐, 棟朝雅晴  電気学会電子・情報・システム部門大会講演論文集(CD-ROM)  2018-  ROMBUNNO.MC1‐5  2018/09/05  [Not refereed][Not invited]
  
• LSTMを用いたユーザの嗜好を反映するBGM自動作曲システム

  岡部太亮, 棟朝雅晴  情報処理学会研究報告(Web)  2018-  (MPS-118)  Vol.2018‐MPS‐118,No.29,1‐2(WEB ONLY)  2018/06/06  [Not refereed][Not invited]
  
• 隠消現実感アプリケーションに基づくエッジコンピューティングの性能推定

  畑徹, 棟朝雅晴  情報処理学会研究報告(Web)  2018-  (MPS-117)  Vol.2018‐MPS‐117,No.23,1‐2 (WEB ONLY)  2018/02/22  [Not refereed][Not invited]
  
• Cgroupsを利用したHadoopにおける落ちこぼれタスクのリソース制限による再現

  岩井良成, 杉木章義, 棟朝雅晴  情報処理学会研究報告(Web)  2017-  (OS-140)  Vol.2017‐OS‐140,No.13,1‐6 (WEB ONLY)  2017/05/09  [Not refereed][Not invited]
  
• 冬道情報サービス構築のためのエッジサーバを用いた分散処理フレームワークの検討

  市居遼平, 棟朝雅晴  情報処理学会研究報告(Web)  2017-  (ITS-68)  Vol.2017‐ITS‐68,No.10,1‐7 (WEB ONLY)  2017/02/21  [Not refereed][Not invited]
  
• Webシステムの性能評価に基づくクラウド資源割当最適化モデルの提案

  齋藤篤志, 山下雅喜, 三浦克宜, 棟朝雅晴  情報処理学会研究報告(Web)  2017-  (MPS-112)  Vol.2017‐MPS‐112,No.13,1‐6 (WEB ONLY)  2017/02/20  [Not refereed][Not invited]
  
• Management of Academic Cloud System at Hokkaido University

  棟朝雅晴  電子情報通信学会技術研究報告  116-  (124(ICM2016 8-23))  85‐86  2016/06/30  [Not refereed][Not invited]
  
• クラウドブローカーシステムにおけるWeb三層システムの最適化数理モデルの検討

  齋藤篤志, 三浦克宜, 棟朝雅晴  電子情報通信学会技術研究報告  116-  (120(NC2016 6-15))  55‐56  2016/06/27  [Not refereed][Not invited]
  
• Building an edge-based process framework for Winter Road Information Service

  市居遼平, 棟朝雅晴, 杉木章義  電子情報通信学会技術研究報告  115-  (504)  83  -88  2016/03/10  [Not refereed][Not invited]
  
• インタークラウド環境下での設計探査支援フレームワークにおける多目的設計最適化の適用

  阿部友哉, 棟朝雅晴  情報処理学会研究報告(Web)  2016-  (MPS-107)  VOL.2016-MPS-107,NO.21 (WEB ONLY)  2016/03/01  [Not refereed][Not invited]
  
• 自動車車載カメラ映像解析による降雪環境下での車両検出及び雪道路面推定手法の提案

  岩坪潤, 棟朝雅晴  情報処理学会研究報告(Web)  2016-  (MPS-107)  VOL.2016-MPS-107,NO.22 (WEB ONLY)  2016/03/01  [Not refereed][Not invited]
  
• 設計者の要求に基づく非劣解分析支援システムの提案

  中野 翔, 渡邉 真也, 千葉 一永, 金崎 雅博, 棟朝 雅晴  計測自動制御学会システム・情報部門学術講演会講演論文集  (2015)  631  -635  2015/11/18  

  多目的最適化によって得られた非劣解集合に対して設計者側の要求に基づいた傾向分析を実現する新たな分析支援システムの提案を行う．本システムは，従来までの相関ルールに基づく分析アプローチを改良したものであり，設計者側からの要求に即したルール抽出に特化することで，設計者の知りたい傾向をピンポイントで抽出することが可能となっている．
• 述語論理式による仕様記述に基づくクラウドブローキングの提案

  三浦克宜, 齋藤篤志, 棟朝雅晴  情報処理学会研究報告(Web)  2015-  (MPS-105)  VOL.2015-MPS-105,NO.6 (WEB ONLY)  2015/09/22  [Not refereed][Not invited]
  
• Toward Realizing a High-Performance Inter-Cloud System

  棟朝雅晴  電子情報通信学会技術研究報告  115-  (140)  43  -48  2015/07/16  [Not refereed][Not invited]
  
• クラウドブローカーのための抽象的なシステム記述の検討

  三浦克宜, 齋藤篤志, 玉家武博, 棟朝雅晴  電子情報通信学会技術研究報告  115-  (112(IBISML2015 1-26))  215  -220  2015/06/16  [Not refereed][Not invited]
  
• インタークラウド環境における仮想システム構築の最適化サービスに関する検討

  玉家 武博, 齋藤 篤志, 三浦 克宜, 棟朝 雅晴  第77回全国大会講演論文集  2015-  (1)  177  -178  2015/03/17  

  クラウドサービスの多様化が進む中で、それぞれのユーザーが自身の要件に適したサービスを選択することが困難になりつつある。そこで本研究では、ユーザーの要件に適した、仮想マシン等からなる仮想システムを自動的に最適化し、構築するクラウドスケジューラの実現に向けた検討を行う。本研究で提案するシステムは，(1) インタークラウド環境におけるそれぞれのクラウドサービスに関する情報を提供するサービス，(2) ユーザーが構築する仮想システムの要求要件に基づいて最適化を行うサービス、(3) インタークラウド環境に仮想システムを自動的に構築するサービス、の3つのWebサービスによって構成される。
• Hadoopを用いた遺伝的アルゴリズムによるDDoS攻撃防止システムの検討

  水越 大貴, 棟朝 雅晴  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告  2014-  (1)  1  -6  2014/12/02  [Not refereed][Not invited]
   

  インターネットにおけるセキュリティ上の脅威の一つとして DDoS 攻撃が深刻な問題になっている.DDoS 攻撃は一般に攻撃元の情報が改竄されているため,攻撃元の特定が非常に困難であり防ぐ事が難しい攻撃だといえる.また,攻撃パターンの学習によるパターンマッチングや,異常トラフィック検知などの手法が研究されているが,DDoS 攻撃において攻撃者はボットネット等を使用し、常に異なるトラフィックパターンの攻撃を仕掛けてくるため、過去のデータの解析から DDoS 攻撃を防ぐ事は非常に難しい.このような背景から,ネットワーク管理者は常に現在どのような攻撃が行われているかを監視、解析し,DDoS 攻撃に対処する必要性に迫られる.しかし,近年ネットワーク上を流れるトラフィック量は急激に増加しており,トラフィックの解析にはかなりの時間かかってしまう事が予測される.そこで本稿では,DDoS 攻撃に対し迅速に対処するシステムを作る事を目的とし,並列分散処理基盤である Hadoop 上での遺伝的アルゴリズムを使用したトラフィックパターンの解析手法を提案する。
• インタークラウド環境下での大規模分散設計最適化のための連携システムの設計

  阿部友哉, 棟朝雅晴  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告  2014-  (18)  1  -2  2014/09/18  [Not refereed][Not invited]
   

  プライベートクラウドやパブリッククラウドを連携させたインタークラウド環境が整備され,仮想的に計算資源を無限に利用できるような環境が実現されつつある.本研究ではそのようなインタークラウド環境を想定して大規模かつ複雑な設計問題を扱う最適化フレームワークを構築する.具体的にはシミュレーションを実行するスパコン,大規模なパラメータサーベイを行うための最適化エンジンや分散データベース,解を視覚的に評価するための可視化装置などの複数のシステムの連携によって,設計問題に関する設計パラメータを統一的に管理,共有し最適化を行う.このフレームワークを構築するにあたって連携システムの詳細設計を行った.
• クラウドPaaS上での多人数インタラクティブ遺伝的アルゴリズムによるスケーラブルな3Dモデリング

  瀬山貴仁, 坂東信太郎, 棟朝雅晴  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告  2014-  (7)  1  -4  2014/07/14  [Not refereed][Not invited]
   

  本論文においては、ユーザーの負担を軽減するために、多人数が協調して解の評価を行うインタラクティブ進化計算の実装について議論する。実装にあたっては、クラウド PaaS(Platform as a Service) 基盤を前提としたスケーラブルなシステムを実現するためのシステム設計を行った。
• インタークラウド環境における大規模分散設計最適化フレームワークに関する検討

  棟朝雅晴  情報処理学会研究報告. BIO, バイオ情報学  2014-  (28)  1  -2  2014/06/18  [Not refereed][Not invited]
   

  プライベートクラウドおよびパブリッククラウドを全国規模で連携させたインタークラウド環境を想定し,大規模かつ複雑な設計問題の設計パラメータに関する情報を,設計者や最適化エンジンが共有,活用しつつ協調して設計を行うフレームワークについて検討する.具体的には,設計パラメータやその評価値等に関する情報を,スケーラブルな分散データベースシステム上に統合管理するとともに,シミュレーションプログラムや可視化システム等の連携を行うフレームワークを,インタークラウド環境における物理・仮想マシン群およびオブジェクトストレージを用いて実現するものである.
• インタークラウド環境における大規模分散設計最適化フレームワークに関する検討(機械学習によるバイオデータマインニング,一般)

  棟朝 雅晴  電子情報通信学会技術研究報告. NC, ニューロコンピューティング  114-  (104)  165  -166  2014/06/18  

  プライベートクラウドおよびパブリッククラウドを全国規模で連携させたインタークラウド環境を想定し,大規模かつ複雑な設計問題の設計パラメータに関する情報を,設計者や最適化エンジンが共有,活用しつつ協調して設計を行うフレームワークについて検討する.具体的には,設計パラメータやその評価値等に関する情報を,スケーラブルな分散データベースシステム上に統合管理するとともに,シミュレーションプログラムや可視化システム等の連携を行うフレームワークを,インタークラウド環境における物理・仮想マシン群およびオブジェクトストレージを用いて実現するものである.
• インタークラウド環境における大規模分散設計最適化フレームワークに関する検討

  棟朝雅晴  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告  2014-  (28)  1  -2  2014/06/18  [Not refereed][Not invited]
   

  プライベートクラウドおよびパブリッククラウドを全国規模で連携させたインタークラウド環境を想定し,大規模かつ複雑な設計問題の設計パラメータに関する情報を,設計者や最適化エンジンが共有,活用しつつ協調して設計を行うフレームワークについて検討する.具体的には,設計パラメータやその評価値等に関する情報を,スケーラブルな分散データベースシステム上に統合管理するとともに,シミュレーションプログラムや可視化システム等の連携を行うフレームワークを,インタークラウド環境における物理・仮想マシン群およびオブジェクトストレージを用いて実現するものである.
• HPCI先端ソフトウェア運用基盤の構築と運用

  三浦信一, 滝澤真一朗, 松岡聡, 棟朝雅晴, 實本英之, 小林泰三  情報処理学会研究報告. [ハイパフォーマンスコンピューティング]  2014-  (30)  1  -6  2014/02/24  [Not refereed][Not invited]
   

  平成 24 年度より運用が開始されている HPCI では,スーパコンピュータ 「京」 や基盤センター群が保有するスーパコンピュータ間の認証基盤統一,データ共有を実現している.しかしながら,既存のスーパコンピュータシステムはバッチキューでジョブ管理されていることや,計算ノードでの管理者権限がないため,OS や分散システムの研究開発を行う CS 系ユーザの利用環境条件を満たさない.また,インターネット上より各種データを取得し,それを用いた計算を行う場合や,得られた成果を外部に公開するには,スーパコンピュータの利用は不向きである.そこで我々は,利用者に対してシステムへの管理者権限を付与する広域分散システムのホスティング機能を提供する,先端ソフトウェア運用基盤を HPCI の枠組みの中で構築し,平成 26 年 4 月より本格運用を開始する.本稿では先端ソフトウェア運用基盤の設計,構築及び運用について紹介する.
• Multi-objective resource allocation optimization of WEB systems considering SLAs in distributed cloud environment

  Takafumi Kawakatsu, Masaharu Munetomo  IPSJ SIG technical reports  2013-  (9)  1  -6  2013/12/04  [Not refereed][Not invited]
   

  We propose a mathematical model for optimal resource allocation of the WEB systems in distributed cloud environment. In the proposed model, we allocate WEB systems with load balancers to cloud systems that satisfy SLAs according to requests from users, which also have a capability of scale-out in increasing the overheads. We solve multi-objective optimization problems considering cost, response time, and throughput using a multi-objective genetic algorithm, and show the effectiveness of the proposed framework through experiments.
• Multi-objective resource allocation optimization of WEB systems considering SLAs in distributed cloud environment

  Takafumi Kawakatsu, Masaharu Munetomo  IPSJ SIG Notes  2013-  (9)  1  -6  2013/12/04  [Not refereed][Not invited]
   

  We propose a mathematical model for optimal resource allocation of the WEB systems in distributed cloud environment. In the proposed model, we allocate WEB systems with load balancers to cloud systems that satisfy SLAs according to requests from users, which also have a capability of scale-out in increasing the overheads. We solve multi-objective optimization problems considering cost, response time, and throughput using a multi-objective genetic algorithm, and show the effectiveness of the proposed framework through experiments.
• Implementation of Multiple Classifier System on MapReduce Framework for Intrusion Detection

  Masataka Mizukoshi, Shintaro Bando, Martin Schlueter, Masaharu Munetomo  IPSJ SIG Notes  2013-  (11)  1  -4  2013/07/15  [Not refereed][Not invited]
   

  Since the data volume from various facilities keeps growing rapidly in recent years, "big data" processing frameworks such as Hadoop have been developed as a scalable architecture to process large amount of data in cloud computing environment. We focus on intrusion detection problems which require large amount of data to be processed in order to detect malicious attacks. In this paper we discuss a Hadoop implementation of a multiple classifier system to enhance performances of the learning process in intrusion detection.
• 広域分散ストレージ検証環境におけるI/O性能評価 (インターネットアーキテクチャ)

  柏崎 礼生, 近堂 徹, 北口 善明, 楠田 友彦, 大沼 善朗, 中川 郁夫, 市川 臭平, 棟朝 雅晴, 高井 昌彰, 阿部 俊二, 横山 重俊, 下條 真司  電子情報通信学会技術研究報告 : 信学技報  112-  (489)  105  -110  2013/03/14  [Not refereed][Not invited]
   

  大規模災害による危機意識の高まりから災害回復(Disaster Recover:DR)を実現するための技術として遠隔地データセンターでのバックアップや分散ストレージに注目が集まっている.現在我々はランダムアクセス性能の高さに特徴のある広域分散ストレージ環境を金沢大学,広島大学,Nilを中心として構築しており,本研究では本環境のI/O性能を評価し,この環境の有用性を示す.
• 広域分散ストレージ検証環境におけるI/O性能評価 (技術と社会・倫理)

  柏崎 礼生, 近堂 徹, 北口 善明, 楠田 友彦, 大沼 善朗, 中川 郁夫, 市川 昊平, 棟朝 雅晴, 高井 昌彰, 阿部 俊二, 横山 重俊, 下條 真司  電子情報通信学会技術研究報告 : 信学技報  112-  (488)  105  -110  2013/03/14  [Not refereed][Not invited]
   

  大規模災害による危機意識の高まりから災害回復(Disaster Recover:DR)を実現するための技術として遠隔地データセンターでのバックアップや分散ストレージに注目が集まっている.現在我々はランダムアクセス性能の高さに特徴のある広域分散ストレージ環境を金沢大学,広島大学,NIIを中心として構築しており,本研究では本環境のI/O性能を評価し,この環境の有用性を示す.
• 広域分散ストレージ検証環境におけるI/O性能評価

  柏崎 礼生, 近堂 徹, 北口 善明, 楠田 友彦, 大沼 善朗, 中川 郁夫, 市川 昊平, 棟朝 雅晴, 高井 昌彰, 阿部 俊二, 横山 重俊, 下條 真司  研究報告インターネットと運用技術（IOT）  2013-  (19)  1  -6  2013/03/07  [Not refereed][Not invited]
   

  大規模災害による危機意識の高まりから災害回復（Disaster Recover: DR）を実現するための技術として遠隔地データセンターでのバックアップや分散ストレージに注目が集まっている．現在我々はランダムアクセス性能の高さに特徴のある広域分散ストレージ環境を金沢大学，広島大学，NIIを中心として構築しており，本研究では本環境のI/O性能を評価し，この環境の有用性を示す．
• Hadoop環境上で動作する研究分野判定ツールの試作

  平島慶典, 三浦克宜, 棟朝雅晴  全国大会講演論文集  2013-  (1)  563  -565  2013/03/06  [Not refereed][Not invited]
   

  本研究では、与えられた論文に対して、的確な研究分野を判定するためのツールを開発する。研究を発展させる上で、関連研究のサーベイは重要であり、そのためには論文の適切な研究分野を知ることは極めて大切である。適切な研究分野を発見する方法として過去の論文と照らし合わせる方法が考えられる。しかしそれには膨大な計算量が掛かるため、逐次処理ではコストがかかる。この問題を解決するために、並列計算を使用している。研究分野の位置づけを行うために、本論文ではMahoutによるクラスタリングを行っており、そのための計算は、Hadoopを利用した並列計算を使用している。
• 単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによる宇宙探査機の多重重力支援軌道最適化

  田中一真, 棟朝雅晴, 赤間清  全国大会講演論文集  2013-  (1)  469  -471  2013/03/06  [Not refereed][Not invited]
   

  複数天体の重力支援を利用した宇宙探査機の軌道最適化は,厳密解の発見が困難な,制約付き非線形多変数関数の最適化問題である.本研究では,欧州宇宙機関で公開されている軌道最適化問題を単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによって解く.
• Design of Authentication System for High Performance Distributed Computing Environment

  合田憲人, 東田学, 坂根栄作, 天野浩文, 小林克志, 棟朝雅晴, 江川隆輔, 建部修見, 鴨志田良和, 滝澤真一朗, 永井亨, 岩下武史, 石川裕  情報処理学会論文誌トランザクション(CD-ROM)  2012-  (2)  2013
• 進化型スワームロボットシステムにおける大規模並列計算環境を用いた非同期処理に関する一考察

  竹中 貴治, 保田 俊行, 大倉 和博, 松村 嘉之, 棟朝 雅晴  精密工学会学術講演会講演論文集  2013-  (0)  775  -776  2013  

  スワームロボットシステムとは多数のロボットが局所的な環境・状況下での相互作用を通して群行動を創発するシステムである．本稿ではニューラルネットをCMA-ESにより最適化するCMA-NeuroESを制御器の設計に運用する．その際，進化の過程で膨大な計算コストが必要となるため，SMP Cluster型の大規模並列計算機で並列・高速化を図る．その上で，並列化を行う上で発生する同期待ち時間に着目し，実行時間短縮について考察する．
• クラウドコンピューティングを俯瞰する

  梶田 将司, 棟朝 雅晴  電子情報通信学会 通信ソサイエティマガジン  7-  (3)  166  -174  2013  [Not refereed][Not invited]
  
• Design of Authentication System for High Performance Distributed Computing Environment

  合田 憲人, 東田 学, 坂根 栄作, 天野 浩文, 小林 克志, 棟朝 雅晴, 江川 隆輔, 建部修見, 鴨志田 良和, 滝澤 真一朗, 永井 亨, 岩下 武史, 石川 裕  情報処理学会論文誌コンピューティングシステム（ACS）  5-  (5)  90  -102  2012/10/15  

  This paper presents design of the authentication system for the High Performance Computing Infrastructure (HPCI), which is currently deployed by the Ministry of Education, Culture, Sports, Science and Technology. The presented authentication system enables single sign-on to computers and shared storages on HPCI by utilizing the authentication mechanism on the Grid, "Grid Security Infrastructure (GSI)", and the identity federation mechanism, "Shibboleth". This paper also presents the experiments conducted on the testbed for the presented authentication system.
• Multi-purpose optimization of resource allocation combined CDN and Web three-layer model in inter-cloud environment

  KAWAKATSU TAKAFUMI, MUNETOMO MASAHARU  情報処理学会研究報告(CD−ROM)  2012-  (3)  ROMBUNNO.MPS-90,NO.13  2012/10/15  [Not refereed][Not invited]
  
• Development of Multiple Precision Arithmetic Software

  YOSHIHARA IKUO, HONDA SHIORI, SAKAMOTO AI, YAMAMORI KUNIHITO, MUNETOMO MASAHARU  Mem Fac Eng Univ Miyazaki  (41)  337-341  2012/07/30  [Not refereed][Not invited]
  
• Multiple-precision Calculation of .PI.

  YOSHIHARA IKUO, SAKAMOTO AI, HONDA SHIORI, YAMAMORI KUNIHITO, MUNETOMO MASAHARU  Mem Fac Eng Univ Miyazaki  (41)  331-335  2012/07/30  [Not refereed][Not invited]
  
• クラウドとビッグデータの活用がもたらすイノベーション (特集 ビジネスの変革を牽引するクラウドソリューション)

  棟朝 雅晴, 堀田 多加志, 田中 誠司  日立評論  94-  (7)  489  -491  2012/07  [Not refereed][Not invited]
  
• Report of a study for efficient multi-parameter survey of OCTA/cognac using ASNARO-RCM

  萩田 克美, 棟朝 雅晴, 上島 豊  計算工学講演会論文集 Proceedings of the Conference on Computational Engineering and Science  17-  4p  2012/05
• 446 Operation Planning of an Energy-Independent-House by a Plant-Shoot Solar Cell Module

  Kawae Osamu, Obara Shinya, Munetomo Masaharu  The Proceedings of the Symposium on Environmental Engineering  2012-  (0)  393  -395  2012  

  In this paper we consider the system to cover all energy by solar cells. System is composed of solar cells, PEFC, water electrolyzer, and heat pump. In this paper, we developed a analysis program by genetic algorithm. And, revealed the capacity of the equipment and two types of operational methods. A result of the analysis, equipment capacity needed in the first method of operating, solar cells is 250m2, PEFC is 8.1kW, water electrolyzer is 22.1kW, heat pump is 14.4kW, amount of hydrogen storage is 106.6kWh, amount of heat storage is 10.2kWh. In addition, equipment capacity needed in the second method of operating, solar cells is 300m2, PEFC is 4.7kW, water electrolyzer is 30.1kW, heat pump is 8.5kW, amount of hydrogen storage is 84.9kWh, amount of heat storage is 21.5kWh. To consider the cost of equipment as the next step.
• Multiple-precision Calculation of π

  Yoshihara Ikuo, Sakamoto Ai, Honda Shiori, Yamamori Kunihito, Munetomo Masaharu  Memoirs of the Faculty of Engineering, University of Miyazaki  41-  (41)  331  -335  2012  [Not refereed][Not invited]
   

  Multiple-precision calculation is necessary for precisely solving scientific engineering problems. Extremely long precision is employed to evaluate the mathematical constant, e.g. π, γ(Euler's constant), e(Nepier's constant) etc. To develope multiple-precision computing software, we try to calculate π with more than one million decimal digits. The proto-type code is verified by performing calculation with numerical examples and evaluated rapidness of calculation. Hother to π with 16,777,199 decimal digit is obtained.
• Development of Multiple Precision Arithmetic Software

  Yoshihara Ikuo, Honda Shiori, Sakamoto Ai, Yamamori Kunihito, Munetomo Masaharu  Memoirs of the Faculty of Engineering, University of Miyazaki  41-  (41)  337  -341  2012  [Not refereed][Not invited]
   

  It is necessary to employ "multiple precision arithmetic" for computing long digit numbers, because numerical representation of computers is usually limited. This paper aims at making prototype software to compute more than one million digit numbers. A long digit number is divided into 2^n short digit numbers, each of which can be calculated by ordinal double precision arithmetic units. The key technique of "multiple precision arithmetic" is based on fast Fourier transform and convolution theorem. The prototype program is verified from the viewpoint of correctness of calculation up to 4 X 10^6 digits and speed up ratio vs theoretical value. The program is applied to calculation of a 10^7 or more digit π.
• The effect of implementation of mixtures of Bayesian Network to dynamic environment problem

  HORI SHIN'YA, MUNETOMO MASAHARU, AKAMA KIYOSHI  情報処理学会研究報告(CD−ROM)  2011-  (3)  ROMBUNNO.MPS-85,NO.16  2011/10/15  [Not refereed][Not invited]
  
• The effect of implementation of mixtures of Bayesian Network to dynamic environment problem

  Shinya Hori, Masaharu Munetomo, Kiyoshi Akama  IPSJ SIG Notes  2011-  (16)  1  -6  2011/09/08  [Not refereed][Not invited]
   

  Bayesian Optimization Algorithm (BOA) can solve wide-spectrum of optimization problems by modeling their probabilistic models with conditional probabilities based on Bayesian networks. BOA succeeds in solving a variety of difficult optimization problems, however, it has not been applied successfully to dynamic environment because it tend to converge at one specific network and cannot adapt to change of probabilistic distributions. In this paper, we propose a BOA that introduces mixture distributions and inheritance of probability distribution of previous generation to adapt to dynamic envir...
• A GPU accelerated Fragment-Based De Novo Ligand Design by a Bayesian Optimization Algorithm

  Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama  研究報告数理モデル化と問題解決（MPS）  2011-  (6)  1  -6  2011/09/08  [Not refereed][Not invited]
   

  De Novo ligand design is an automatic fragment-based design of molecules within a protein binding site of a known structure. A Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, is introduced to join predocked fragments with a user-supplied list of fragments. A novel feature proposed is the simultaneous optimization of force field energy and a term enforcing 3D-overlap to known binding mode(s). The performance of algorithm is tested on Liver X receptors (LXRs) using a library of about 14,000 fragments and the binding mode of a known heterocyclic phenyl acetic acid to bias the design. We further introduce the use of GPU (Graphical Processing Unit) to overcome the excessive time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragment sets and target receptors for more complex instances. The Results show how the nVidia's Tesla C2050 GPU was utilized to enable the generation of complex agonists effectively. In fact, eight of the 1809 molecules designed for LXRs are found in the ZINC database of commercially available compounds.De Novo ligand design is an automatic fragment-based design of molecules within a protein binding site of a known structure. A Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, is introduced to join predocked fragments with a user-supplied list of fragments. A novel feature proposed is the simultaneous optimization of force field energy and a term enforcing 3D-overlap to known binding mode(s). The performance of algorithm is tested on Liver X receptors (LXRs) using a library of about 14,000 fragments and the binding mode of a known heterocyclic phenyl acetic acid to bias the design. We further introduce the use of GPU (Graphical Processing Unit) to overcome the excessive time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragment sets and target receptors for more complex instances. The Results show how the nVidia's Tesla C2050 GPU was utilized to enable the generation of complex agonists effectively. In fact, eight of the 1809 molecules designed for LXRs are found in the ZINC database of commercially available compounds.
• RL-004 Deployment of Contents Management Systems on Hokkaido University Academic Cloud

  Munetomo Masaharu, Takai Yoshiaki  情報科学技術フォーラム講演論文集  10-  (4)  15  -18  2011/09/07
• Design of Advanced Software Deployment Infrastructure in HPCI Wide-area Distributed Environment

  TAKIZAWA SHIN'ICHIRO, MUNETOMO MASAHARU, UNO ATSUYA, KOBAYASHI TAIZO, JITSUMOTO HIDEYUKI, MATSUOKA SATOSHI, MATSUOKA SATOSHI, ISHIKAWA YUTAKA  情報処理学会研究報告(CD−ROM)  2011-  (2)  ROMBUNNO.HPC-130,NO.68  2011/08/15  [Not refereed][Not invited]
  
• Design of Advanced Software Deployment Infrastructure in HPCI Wide-area Distributed Environment

  Shinichiro Takizawa, Masaharu Munetomo, Atsuya Uno, Taizo Kobayashi, Hideyuki Jitsumoto, Satoshi Matsuoka, Yutaka Ishikawa  IPSJ SIG Notes  2011-  (68)  1  -7  2011/07/20  [Not refereed][Not invited]
   

  The purpose of HPCI, which will be operated from autumn 2012, is to support HPC researchers to use K supercomputer, and its initial services are a federated authentication and global file sharing between K and supercomputers provided by computer centers in Japan. However, supercomputers are not suitable for HPC system researchers as their operations do not give users enough privileges. We design the advanced software deployment infrastructure that hosts distributed systems where researchers can have administrator privileges. We introduce the design of the system and a precedent system imple...
• A Light Framework for the Unified Representation and Execution of Variant Tasks in a Grid Based Environment

  WAHIB MOHAMED, MUNAWAR ASIM, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  79-  (9)  I1  -I11  2010/07/12  [Not refereed][Not invited]
   

  Grid computing has gained a wide interest from the research community over the past one and a half decade. The immense effort has resulted in mature tools and technologies for grid computing. The utilization of experience and tools of grid computing in the next generation of distributed systems (e.g. cloud com-puting) is a logical step. However, many problems that come along with grid computing do limit such an effort. Among these problems is the sophistication of each production grid to a specific task type, size and dependency. In other words, grid computing in practice up to the moment c...
• An effective Bayesian Network Construction Method for BOA

  HORI SHIN'YA, MUNETOMO MASAHARU, AKAMA KIYOSHI  情報処理学会研究報告(CD−ROM)  2009-  (6)  ROMBUNNO.MPS-77,23  2010/04/15  [Not refereed][Not invited]
  
• An effective Bayesian Network Construction Method for BOA

  堀 伸哉, 棟朝 雅晴, 赤間 清  情報処理学会研究報告  2009-  (6)  1  -7  2010/04  [Not refereed][Not invited]
   

  本論文は BOA の改良型アルゴリズム、EBOA （Effective BOA） を提案する。EBOA は BOA のベイジアンネットワーク構築フェイズにおいて、探索する遺伝子ノード数をエントロピーの値によってクラスタリングし、それぞれのクラスターでベイジアンネットワークを構築することで遺伝子の探索時間を減少させる。また、これと同時にエントロピーの値による探索遺伝子数の絞込みも導入する。これら二つの手法を取り入れた EBOA は BOA において問題となる多大な実行時間を短縮することで複雑で巨大な問題の最適化を行うことが可能となる。This paper proposes an Effective Bayesian Optimization Algorithm (EBOA) which improves network construction process of BOA. EBOA performs clustering of locus nodes based on their entropy measures and at the same time, removes loci that are not necessary to be modeled based on their entropy. After the clustering, it constructs a Bayesian Network in each cluster to reduce the running time for searching networks for BOA to solve large and complex optimization problems.
• An effective Bayesian Network Construction Method for BOA

  Shinya Hori, Masaharu Munetomo, Kiyoshi Akama  IPSJ SIG Notes  2010-  (23)  1  -7  2010/02/25  [Not refereed][Not invited]
   

  This paper proposes an Effective Bayesian Optimization Algorithm (EBOA) which improves network construction process of BOA. EBOA performs clustering of locus nodes based on their entropy measures and at the same time, removes loci that are not necessary to be modeled based on their entropy. After the clustering, it constructs a Bayesian Network in each cluster to reduce the running time for searching networks for BOA to solve large and complex optimization problems.
• A Grid based Unified Framework for Optimization

  MUNAWAR ASIM, WAHIB MOHAMED, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  69-  (41)  23  -26  2008/05/09  [Not refereed][Not invited]
   

  This paper presents a Service Oriented Architecture (SOA) compliant Problem Solving Environment (PSE) that allows the user to implement any metaheuristics based algorithm over a Grid. We call this framework a Grid based Unified Framework for Optimization (GridUFO). GridUFO provides a unified approach for sharing and using metaheuristics algorithms (solvers) and objective functions over a Grid in an easiest possible "plug & play" manner. In this way the user can take all the advantages of the Grid without taking into consideration any of the complexities posed by the Grid environment. The framework is accessible to the user through a Web service or through a fully integrated 2nd generation Web portal. GridUFO provides well-defined interfaces between the user-programmed objective functions and solvers. We also present MetaHeuristics Markup Language (MHML), an XML based language that acts as an interface between the user and the framework. In this paper we will discuss the design and implementation of GridUFO in detail. Moreover, we will talk about our experience of working with Grids, and we will also make some recommendations for future research.
• An Empirical Study on BOA which Introduces Scatter Search

  SATAKE YUTA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  68-  (17)  109  -112  2008/03/04  [Not refereed][Not invited]
   

  Bayesian Optimization Algorithm (BOA) builds its probabilistic model which represents distribution of promising solutions and generates new solutions based on the model. Because BOA detects interdependent loci by using the model, it can solve a wide spectrum of optimization problems effectively. BOA which introduces local search in order to enhance its performance is already proposed. However, they did not use Scatter Search, which can create new search points effectively, as local search. In this paper, we propose BOA which introduces scatter search and discuss its effectiveness.
• Parallelization of a genetic algorithm using linkage identification and context dependent crossover

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG technical reports  2007-  (128)  171  -174  2007/12/20  [Not refereed][Not invited]
   

  Parallelized competent genetic algorithms (cGAs) which can detect problem structures automatically can give us problem solving environments for a wide spectrum of real-world problems. As such algorithms, the DBOA, PBOA and parallel BOA which are based on BOA and pLINC which is based on LINC had been proposed. However, model buildings in the parallelized BOAs are performed under some restrictions or using backtracking to obtain feasible models. While pLINC can be parallelized in a simpler way, the original LINC spends huge number of fitness evaluations. In this paper, we try to parallelize D^5 which can also be parallelized in a simple way and requires relatively small number of fitness evaluations. We also try to parallelize population evolution with context dependent crossover (CDC) which can combine overlapping building blocks effectively. Moreover, we perform some experiments to compare the paralleled D^5-GA+CDC and other cGAs to reveal their properties.
• Parallelization of a genetic algorithm using linkage identification and context dependent crossover

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  67-  (128)  171  -174  2007/12/20  [Not refereed][Not invited]
   

  Parallelized competent genetic algorithms (cGAs) which can detect problem structures automatically can give us problem solving environments for a wide spectrum of real-world problems. As such algorithms, the DBOA, PBOA and parallel BOA which are based on BOA and pLINC which is based on LINC had been proposed. However, model buildings in the parallelized BOAs are performed under some restrictions or using backtracking to obtain feasible models. While pLINC can be parallelized in a simpler way, the original LINC spends huge number of fitness evaluations. In this paper, we try to parallelize D^5 which can also be parallelized in a simple way and requires relatively small number of fitness evaluations. We also try to parallelize population evolution with context dependent crossover (CDC) which can combine overlapping building blocks effectively. Moreover, we perform some experiments to compare the paralleled D^5-GA+CDC and other cGAs to reveal their properties.
• A Proposal of Crossover Method for Complex Building Blocks Overlapping

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  情報処理学会論文誌数理モデル化と応用（TOM）  48-  (15)  23  -33  2007/10/15  [Not refereed][Not invited]
   

  In order to realize effective genetic algorithms, there have been several techniques to identify linkage sets of loci to form a building block (BB) (Heckendorn, et al.). By contrast, the way to realize effective crossover from the linkage information given by such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu, et al. (2005) is the first and only known research. However it cannot perform well for problems with complexly overlapping BBs due to BB disruptions and insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings to determine which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. Because the proposed method considers the context of parental strings, it is called context dependent crossover (CDC). Combining a scalable linkage identification technique and the CDC, an effective algorithm for problems with overlapping BBs is provided. Moreover, to test the proposed method, we design test functions with controllable complexity of overlaps.
• Consideration of Estimation of Distribution Algorithms employing Simulated Annealing

  MAEDA HARUKI, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  64-  (43)  13  -16  2007/05/17  [Not refereed][Not invited]
   

  Estimation of Distribution Algorithms(EDAs) build a probabiblistic model which reflects promising solutions and generate new solutions using the model. Considering the dependencies between the variables with the model, they can slove GA-difficult problems. On the other hand, EDAs have a drawback they need extensive computational cost for building the model. While the development of such optimization methods is advanced, the hybridizations of these methods and local search methods are widely studied. In this paper, we propose a hybrid algorithm of Bayesian Optimization Algorithm(BOA), which is one of EDAs, and a local search employing Simulated Annealing(SA).
• Asim Munawar, Masaharu Munetomo, Akama Kiyoshi

  1191  -1198  2007  [Not refereed][Not invited]
  
• Considering ECGA which Introduces Tabu Search

  SATAKE YUTA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG technical reports  2006-  (135)  61  -64  2006/12/21  [Not refereed][Not invited]
   

  Extended Compact Genetic Algorithm (ECGA) builds its probabilistic model which represents distribution of promising solutions and generates new solutions based on the model. Because ECGA detects interdependent loci by using the model, it can solve a wide spectrum of optimization problems effectively. ECGA which introduces neighbourhood search in order to enhance its performance is already proposed. However, they did not use tabu search, which is one of the most effective neighbourhood searches, as neighbourhood search. In this paper, we propose ECGA which introduces tabu search and consider its effectiveness.
• Considering ECGA which Introduces Tabu Search

  SATAKE YUTA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  62-  (135)  61  -64  2006/12/21  [Not refereed][Not invited]
   

  Extended Compact Genetic Algorithm (ECGA) builds its probabilistic model which represents distribution of promising solutions and generates new solutions based on the model. Because ECGA detects interdependent loci by using the model, it can solve a wide spectrum of optimization problems effectively. ECGA which introduces neighbourhood search in order to enhance its performance is already proposed. However, they did not use tabu search, which is one of the most effective neighbourhood searches, as neighbourhood search. In this paper, we propose ECGA which introduces tabu search and consider its effectiveness.
• Tabu Searchを導入したECGAについての検討

  佐竹 佑太, 棟朝 雅晴, 赤間 清  情報処理学会研究報告  2006-  (135)  61  -64  2006/12/21  [Not refereed][Not invited]
  
• Considering Computational Cost of Probabilistic Model-Building Genetic Algorithms which Introduce Local Search

  SATAKE YUTA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  59-  (56)  25  -28  2006/05/25  [Not refereed][Not invited]
   

  Probabilistic Model-Building Genetic Algorithms (PMBGAs) build their probabilistic models which represent distribution of promising solutions and generate new solutions based on the models. Although PMBGAs can solve a wide spectrum of optimization problems effectively, their probabilistic model-buiding processes need extensive computational cost. On the other hand, in PMBGAs which introduce local search, although the number of evaluations is high, they can reduce the cost to build models. In this paper, we consider the relation of the number of evalations and the cost to build models in PMBGAs which introduce local search.
• Generation of Correct Parallel Programs for Solving Constraint Satisfaction Problems

  SAITO YUSUKE, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  2006-  (20)  103  -108  2006/02/27  [Not refereed][Not invited]
   

  Based on Equivalent Transformation (ET) computation model, a theory of parallel program generation is proposed, where correct parallel programs are generated from a set of ET-rules that transform a set of definite clauses that represents a given problem. Correctness of the method is explained. Usefulness of the method is partly shown by experiments of a parallel program generated for a constraint solving problem.
• Generation of Correct Parallel Programs for Solving Constraint Satisfaction Problems

  SAITO YUSUKE, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  167-  (20)  103  -108  2006/02/27  [Not refereed][Not invited]
   

  Based on Equivalent Transformation (ET) computation model, a theory of parallel program generation is proposed, where correct parallel programs are generated from a set of ET-rules that transform a set of definite clauses that represents a given problem. Correctness of the method is explained. Usefulness of the method is partly shown by experiments of a parallel program generated for a constraint solving problem.
• Applying the D^5-GA for problems with overlapping building blocks

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  2005-  (93)  65  -68  2005/09/21  [Not refereed][Not invited]
   

  The D^5-GA [4] detects interdepended loci and use the information as a guidance on exploration. The existing D^5-GA divides all loci into exclusive sets-called linkage sets-of loci which are linked tightly to construct a building block and exchanges loci in a same set simultaneously to enhance efficient building block mixing. However, some real-world problems have overlapping building blocks. In this paper, we extend the structure of the linkage sets to apply the D^5-GA for problems with overlapping building blocks. In addition, we modify a crossover method proposed by Yu et al. [6] to achieve (1) smaller BB disruptions and (2) larger BB exchanges.
• Linkage Identification for Real-Coded Genetic Algorithms based on Additive Decomposability and Difference Signature Independency of Objective Function

  TEZUKA MASARU, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  53-  (20)  9  -12  2005/03/09  [Not refereed][Not invited]
   

  In the case that a problem is decomposable to a number of sub-problems which can be optimized independently, the problem is solved effectively by optimizing sub-problems separately. In optimization problems by means of genetic algorithms, a set of loci of which each sub-problem consists is called linkage group. Linkage identification is the method which recognizes linkage groups. In this paper, we define the linkage of Real-Coded GAs clearly. Then we propose two new linkage identification methods, LINC-R and LIDI-R, directly based on the definition. LINC-R is based on additive decomposability of a objective function and LIDI-R is based on the independency of the signature of difference. These methods effectively identify linkages. Parallel optimization of the linkage groups has a capability to obtain better solutions in smaller number of function evaluations than conventional GAs.
• Structure Prediction of Protein by BOA with parallel network construction

  MURAO NAOYA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  162-  (19)  67  -72  2005/03/07  [Not refereed][Not invited]
   

  Bayesian optimization algorithm (BOA) is an advanced optimization algorithm that effectively solves GA-difficult problems in which it is difficult to ensure tight encoding. BOA constructs Bayesian networks based on probabilistic distributions of current promising solutions, and generates next population based on the obtained networks. However, computational cost of the estimation depends on the problem size, and is known the calculation cost increases rapidly along increasing the problem size. In our previous study, we proposed a BOA with parallelized Bayesian network construction. In this paper, we try to solve proteins structure prediction problems that minimize the structual energy by employing BOA with the parallel network construction, and investigate the effectiveness of our approach.
• リンケージ同定GAを導入した波長割当方式の評価(ネットワークプロトコル)

  釘本 健司, 棟朝 雅晴, 赤間 清  情報処理学会研究報告. EIP, [電子化知的財産・社会基盤]  2004-  (89)  63  -69  2004/09/02  [Not refereed][Not invited]
   

  次世代のインターネットの基盤ネットワークとして,WDM(Wavelength Division Multiplexing)に基づいたフォトニックネットワーク(WDM-PN)が注目されている.このWDM-PNにおいては,物理トポロジ上に光パスを割り当てることで論理トポロジが構成される.限られた波長を効率良く使って論理トポロジを構成する問題は,波長割当問題と呼ばれ,制約つき組合わせ問題の一つである.本稿では,リンケージ同定を導入した遺伝的アルゴリズムの波長割当問題への適用を試みたので報告する.本アルゴリズムでは,トラフィック全体の遅延の最小化を目的とし,リンケージ同定手法としてLINC(Linkage Identification by Nonlinearity Check)およびLIEM(Linkage Identification with Epistasis Measure)を用いた.計算機シミュレーションにより単純遺伝的アルゴリズムとの比較を行ない,LIEMの効果を確認した.
• An Evaluation of WDM Wavelength Assignment using Genetic Algorithm with Linkage Identification

  Kugimoto Takeshi, Munetomo Masaharu, Akama Kiyoshi  IPSJ SIG Notes  2004-  (89)  63  -69  2004/09/02  [Not refereed][Not invited]
   

  Wavelength Division Multiplexing (WDM) is a technology which multiplexes the light of different wavelength to single optical fiber. It allows more efficient use of an optical firer, but also allows new network feature - virtual topology. Virtual topology is the connection graph whose links are lightpaths. In such the WDM network, virtual network topology can be dynamically constructed by changing the combination of the wavelength assignment in physical topology. The wavelength assignment problem is a combinational optimization problem. Heuristic method such as genetic algorithm (GA) is often used to solve such an optimization problem. In this paper, we consider the Linkage Identification based GA approach. Linkage Identification is a sort of technique to detect Building Block in genes. The results obtained from Linkage Identification based GA approach are compared with ordinary simple GA to illustrate the effectiveness of proposed approach.
• A-024 Real-Coded Genetic Algorithm to Optimize Fitness Function with Sampling Error

  Tezuka Masaru, Munetomo Masaharu, Akama Kiyoshi  情報科学技術フォーラム一般講演論文集  3-  (1)  55  -56  2004/08/20  [Not refereed][Not invited]
  
• Empirical Investigations on the parallelized Bayesian Optimization Algorithm

  MURAO NAOYA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  157-  (20)  169  -174  2004/03/01  [Not refereed][Not invited]
   

  The Bayesian optimization algorithm is an advanced search technique generating population of string by estimating distribution of promising solutions, which can solve difficult problems efficiently that simple Genetic algorithm cannot solve. However, since computational cost for estimating distribution is large, research for parallelizing of BOA is necessary. Although Parallel BOA is experimented in the previous research, it is performed on a small number of processors. In this paper, empirical investigation on the performance of parallel BOA is performed in detail.
• Performance comparisons between parallel linkage identification and parallel BOA

  MURAO NAOYA, MUNETOMO MASAHARU, AKAMA KIYOSHI  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告  47-  (0)  57  -60  2003/12/11  [Not refereed][Not invited]
  
• Modeling dependency from distributions of strings classified according to fitness change

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告  47-  (0)  61  -64  2003/12/11  [Not refereed][Not invited]
  
• Performance comparisons between parallel linkage identification and parallel BOA

  MURAO NAOYA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  47-  (122)  57  -60  2003/12/11  [Not refereed][Not invited]
   

  The linkage identification and the Bayesian Optimization Algorithm are proposed to solve GA-difficult problems. These algorithms are competent, while their computational cost is high. Recently, parallelized version of linkage identification and BOA are studied to decrease time to obtain solutions. However, it is no clear which algorithms should we use to solve the problem. In this paper, we compare the performance of parallel linkage identification to that of parallel BOA, and then we consider a relation between the nature of problem and their performances to obtain a guideline to select parallel GAs.
• Modeling dependency from distributions of strings classified according to fitness change

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  47-  (122)  61  -64  2003/12/11  [Not refereed][Not invited]
   

  Genetic Algorithms (GAs) can perform effectively by identifying a set of loci tightly linked and strongly interdepended to form a same building block. Various methods are alreadly proposed to detect such dependencies. Some of them investigate the fitness changes from the perturbation of gene value and some others estimate the distribution of strings in promising sub population. In this paper, we propose a new method combining both of them, which detects dependencies through the estimation of the distribution of strings classified according to fitness change. The proposed method can detect dependencies accurately by a little more than O(l) fitness evaluations.
• Investigations on Parallelizing Methods of Evolutionary Computation

  MURAO NAOYA, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  93-  (29)  161  -166  2003/03/11  [Not refereed][Not invited]
   

  Parallel genetic algorithm (PGA) is an active research area in evolutionary computation and a number of papers have been published, however, relation between the nature of the problems and the method to be applied to solve them. Most papers deal with a tailered version of PGA to solve a specific problem. In this paper, we perform empirical investigations on the relation between characteristics of problems based on building blocks weights and selection of PGA methods. We also compare conventional methods with a novel approach of PGA based on linkage identification. Final goal of the paper is to show a guideline to users choosing one of the PGA methods based on the characteristics of the problems to be solved.
• MAN Design by Hierarchical Linkage Genetic Algorithm

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  110-  (108)  73  -78  2002/11/21  [Not refereed][Not invited]
   

  Metropolitan area network design is a difficult combinatorial optimization problem, which generates an optimal network topology that satisfies geographical constraints, user traffic constraints, etc. from a huge number of candidates. In the network design problems, simple GAs sometimes fail to recombine building blocks, which leads to unappropriate solutions. In the previous work [7], a GA based on linkage identification could solve this problem effectively, which identifies a set of loci belonging to a same linkage group to exchange building blocks accurately. In this paper, single layer linkage identification has been extended to hierarchical one, which considers interdependence of building blocks in a recursive manner, instead of identifying interdependence of loci.
• A Genetic Algorithm using Linkage Identification for Metropolitan Area Network Design

  TSUJI MIWAKO, MUNETOMO MASAHARU, AKAMA KIYOSHI  IPSJ SIG Notes  39-  (36)  9  -12  2002/05/10  [Not refereed][Not invited]
   

  In genetic algorithms, it is important to encode strings ensuring tight linkage for their huilding blocks. in network design prohlems, however, it is difficult to encode strings appropriately because network design is dependent not only on geographical constraints hut also on other complex factors such as bias on traffic demands, routing policy, and so on. Although there's many applications of genetic algorithms to network topology design, most of them haven't paid attention to tight encoding of building blocks, or considered only geographical characteristics. In order to realize tight linkage among loci and realize effective genetic search, this paper introduces LIEM (Linkage Identification with Epistasis Measure) - a technique for identifying linkage sets, sets of loci tightly liked to form building filocks - to realize effective network design. Through empirical studies, we show the effectiveness of the network design with the LIEM compared to that with conventional genetic algorithms.
• Designing a Distributed Algorithm Using Genetic Algorithms for Bandwidth Allocation -Recovery Mechanism from Node Failure -

  小林 英博, 棟朝 雅晴, 赤間 清, 佐藤 義治  マルチメディア通信と分散処理ワークショップ論文集  2000-  (15)  91  -96  2000/12/06
• Designing a Distributed Algorithm Using Genetic Algorithms for Bandwidth Allocation : Recovery Mechanism from Link Failure

  KOBAYASHI Hidehiro, MUNETOMO Masaharu, AKAMA Kiyoshi, SATO Yoshiharu  IPSJ SIG Notes  100-  (102)  7  -12  2000/05/26  [Not refereed][Not invited]
   

  Network resources are limited in their capacity, moreover fast high capacity communication links are expensive. Thus bandwidth allocation and efficient usage of limited resources are important. Previously, GRA(Genetic Routing Algorithm)has been proposed as a bandwidth allocation with genetic algorithm. This algorithm is centralized algorithms and execute localizing optimizing, in case of trouble it is impossible to allocate bandwidth. Therefore we suggested distributed-GRA(D-GRA)previously, however this is imperfect about communication links failure and recovering from trouble. Then, in this paper, we eill improve D-GRA to recover from communication link failure.
• Controling Frequency of Route Estimation in Routing Algorithm

  YAMAGUCHI Naohiko, MUNETOMO Masaharu, AKAMA Kiyoshi, SATO Yoshiharu  IPSJ SIG Notes  100-  (102)  69  -74  2000/05/26  [Not refereed][Not invited]
   

  Expansion of computer networks such as the Internet is so rapid and traffic over the networks is increasing along their expansion. Therefore, it is important to utilize network resources efficiently and reduce network latency by distributing communication packets among alternative routes. To realize effective load balancing, we have proposed a network routing algorithms employing genetic algorithms to generate alternative routes and observe loads of links along the routes adaptively. In this paper, we will focus on evaluation strategy of routes. Changing evaluation strategy and frequency of observations, we examine their effects on overall network load status.
• 動的負荷分散機構を有する分散型経路制御アルゴリズム

  山口 直彦, 棟朝 雅晴, 佐藤 義治  第60回全国大会講演論文集  2000-  (1)  449  -450  2000/03/14
• 遺伝的アルゴリズム4<分担 : 北野 宏明 編>

  産業図書  2000  [Not refereed][Not invited]
  
• Bandwidth Allocation using Genetic Algorithms

  KOABYASHI Hidehiro, MUNETOMO Masaharu, SATO Yoshiharu  IPSJ SIG Notes  95-  (94)  91  -96  1999/05/27  [Not refereed][Not invited]
   

  Effective bandwidth allocation becomes essential to utilize network resources, espacially in large networks. In allocation problems, it is difficult to obtain optimal solution in reasonable computational cost because they are classified into combinatorial optimization problems. Mario Gerlra et. al[1] proposed an allocation algorithm that minimize the mean packet delay. In this paper, we try to solve a multi-objective optimization problem that minimizes the delay and also minimizes its variance. We employ genetic algorithms with multi-objective selection strategies in order to obtain a sef of Pareto optima.
• Inter-AS Routing with Evolutionary methods

  YAMAGUCHI Naohiko, MUNETOMO Masaharu, SATO Yoshiharu  IPSJ SIG Notes  95-  (94)  97  -102  1999/05/27  [Not refereed][Not invited]
   

  In this paper, we propose an adaptive inter-AS routing algorithm that has a load balancing mechanism that distributes communication packets among alternative routes generated by genetic operators. The Border Gateway Protocol (BGP) widely employed for inter AS routing does not take an adaptive approach: it cannot determine routes based on current load status of the network although it distributes packets among alternative routes with the same distance measure. Our algorithm called GIAR (Genetic Inter AS Routing) observes load status of links along the alternative routes adaptively to realize load balancing among them by distributing packets probabilistically among them. To realize robust observation of routes in inter-AS routing, we introduce a threshold policy that classifies load status of links based on its queue length.
• Identifying linkage groups by nonlinearity/non-monotonicity detection

  MUNETOMO Masaharu  Proceedings of the 1999 Genetic and Evolutionary Computation Conference  1999
• A prediction algorithm for process resurce usage based on a state transition model

  Moriguchi Shuichi, Munemoto Masaharu, Sato Yoshiharu  全国大会講演論文集  56-  (0)  58  -59  1998/03/17  [Not refereed][Not invited]
  
• A migration scheme for the genetic adaptive routing algorithm

  M Munetomo, Y Takai, Y Sato  1998 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-5  2774  -2779  1998  [Not refereed][Not invited]
   

  This paper presents a string migration scheme for an adaptive network routing algorithm called a genetic routing algorithm[10] which employs genetic operators to create alternative routes in a routing table. String migrations are employed usually in islands model of parallel or distributed genetic algorithms, which exchange strings among subpopulations to accelerate their convergence. We propose a tailored version of string migration for the genetic routing algorithm in order to realize effective information exchanges among nodes to have optimal route with less communication overhead in the network.
• Identifying linkage by nonlinearity check

  MUNETOMO Masaharu  Technical Report IlliGAL Report  1998
• Designing a genetic algorithm using the linkage identification by nonlinearity check

  MUNETOMO Masaharu  Technical Report IlliGAL Report  1998
• A Meeting Scheduling System Supported by Mobile Agents

  TOMIKAWA Yuki, TAKAI Yoshiaki, MUNETOMO Masaharu, YAMAMOTO Tsuyoshi  IPSJ SIG Notes  85-  (104)  133  -136  1997/11/06  [Not refereed][Not invited]
   

  When we negotiate an urgent issue through WAN such as the Internet, the unpredictable network latency may cause inefficient communication between negotiators. Because of the rapid traffic increase of the Internet, it is more and more difficult to communicate quickly. Mobile agents are programs that can autonomously travel across a network. Arriving at the remote computer, they can interact with other agents locally. Hence, the mobile agents are suitable for negotiation through WAN. In this paper we discuss a framework for making out a meeting schedule by using mobile agents. We implement a prototype system using Aglets, and we discuss agent's ability for more available communication system.
• A Load Sharing Mechanism of Adaptive Routing Algorithms

  MUNETOMO Masaharu, TAKAI Yoshiaki, SATO Yoshiharu  IPSJ SIG Notes  80-  (13)  205  -210  1997/01/30  [Not refereed][Not invited]
   

  This paper presents an adaptive routing algorithm which has a load balancing mechanism among alternative paths, and shows the effectiveness of the algorithm through simulation experiments. Conventional routing algorithms broadcast information on routing tables or link status in a network, which leads to consume much communication cost when the becomes large. A routing algorithm we propose generates alternative paths and perform evaluation of communication delay only for paths frequently used. This mechanism greatly reduces communication cost for information exchanging of the routing. In the algorithm, we employ genetic algorithms in generating alternative paths among which we distribute communication packets to ensure load balancing. We perform simulation experiments using a simulator of network communications and the result of the experiments says that an effective routing is achieved by less communication cost.
• Adaptive Source Routing Using a Genetic Algorithm

  MURAI Yasunori, MUNETOMO Masaharu, TAKAI Yoshiaki  IPSJ Technical Report  79-  (108)  43  -48  1996/11/14  [Not refereed][Not invited]
   

  We propose an adaptive algorithm for network routing and show the effectiveness of it through simulation experiments. The algorithm, which is based on a genetic algorithm, dynamically changes routes to keep the communication delay minimal by observing the communication delay of the packets. Every router on the network has the populations of genes which represent the candidates of routes. We use the mean communication delay along the routes to calculate genetic fitness of them. The result of the experiments shows that the algorithm is able to fit a large scale network and performance of it strongly depends on initial conditions of the genes.
• Adaptive Routing using a Genetic Algorithm

  Murai Yasunori, Munetomo Masaharu, Takai Yoshiaki  全国大会講演論文集  52-  (0)  121  -122  1996/03/06  [Not refereed][Not invited]
   

  計算機ネットワークの拡大とトラヒックの増大に伴い、通信経路を決定するルーティング手法が急速にその重要性を高めている。本稿では遺伝的アルゴリズムを応用して、ネットワーク状態の変化に適応し、動的に経路選択を行うルーティング手法を提案する。経路選択の目的は平均の通信遅延時間を最小にすることであるが、これに要する付加的な制御情報の通信もネットワークのトラヒックに影響を与えるため、その通信は最小限に押さえられる必要がある。
• Evaluation of a Dynamic Load Balancing Algorithm by using Multicast on a Massively Parallel Processor

  Ikeda Masaki, Munetomo Masaharu, Takai Yoshiaki  全国大会講演論文集  52-  (0)  161  -162  1996/03/06  [Not refereed][Not invited]
   

  分散システムの利用率を向上させるためには、システムを構成する計算機間で負荷を平均化する必要がある。動的負荷分散アルゴリズムは負荷の重い計算機から負荷の軽い計算機へタスクを転送することでシステム全体として負荷の平均化をはかる。少ない通信量で効果的なタスク転送を行なうために、タスク転送要求の送出先を複数指定するマルチキャストを導入した手法が提案されている。 一方、局所メモリを持つ自立した計算ノードが専用の高速通信ネットワークにより相互結合されたMIMD型の並列計算機である超並列計算機は、高速な並列計算機を安価に実現するアーキテクチャとして近年注目を集めており、数多くの開発例が存在する。 そこで本論文では、マルチキャストによる動的負荷分散アルゴリズムを超並列計算機へ実装し、そのアルゴリズムの性能評価を行なうことで、超並列計算機上でのアルゴリズムの特性を調べる。具体的には、マルチキャストを用いた動的負荷分散アルゴリズムのシミュレータをParallel-Ware(ExPress)の通信ライブラリを用いて超並列計算機SR-2001上に実現し、シミュレーション実験を通してアルゴリズムの性能評価を行なう。
• An Application of a Genetic Algorithm to Stochastic Learning

  MUNETOMO Masaharu, TAKAI Yoshiaki, SATO Yoshiharu  The Transactions of the Institute of Electronics,Information and Communication Engineers.  79-  (2)  230  -238  1996/02/25  [Not refereed][Not invited]
   

  確率的な環境への適応学習を行う場合, 確率学習オートマトンに代表される強化学習が一般に用いられるが, 選択可能な行動の数が多くなった場合に最適解への収束が著しく遅くなるという欠点がある. 本論文では遺伝的アルゴリズムを応用することで, 強化学習における収束速度の問題点を解消する手法を提案する. 提案するアルゴリズムStGA(Stochastic Genetic Algorithm)においては, すべての可能な行動の中から少数の行動を集団としてサンプリングし, その集団に対して確率学習オートマトンを適用することで強化学習の収束速度を向上させる. 更に, 遺伝的操作を用いて集団内に含まれていない新たな行動を生成することを通して集団の内容を更新し, 最適な行動を効率良く探索する. StGAの収束性を証明するため, 確率学習オートマトンのε-optimalityをもとにした理論的解析を行う. 更にシミュレーション実験により, 可能な行動の数が多い場合におけるStGAの有効性を示す.
• Emergence of Cooperative Strategies in a Multi Agent Game

  Tomikawa Yuki, Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  情報処理学会研究報告. 人工知能研究会報告  95-  (105)  25  -30  1995/11/07  [Not refereed][Not invited]
   

  An SLA (Stochastic Learning Automaton) with huge number of possible Strategies takes a lot of time to converge. To avoid this problem ; an StGA (Stochastic Genetic Algorithm) was proposed to accelerate the learning process of the SLA. In this paper, we apply the StGA to strategy acquisition in games played by the groups of agents. The agents have implicit communication capability where there is no a pri ori meaning defined for the messages. We discuss the possibility of emergence of cooperation strategies through simulation experiments.
• Dynamic Load Balancing with Genetic Algorithms on a UNIX Network

  Yamashita Takayuki, Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  全国大会講演論文集  50-  (0)  249  -250  1995/03/15  [Not refereed][Not invited]
   

  複数の計算機をLANで接続して資源の共有を図る分散システムにおいて、計算機間で負荷の分散を行うことにより、応答時間の短縮や資源利用率の改善など、システム性能の向上を図ることができる。この目的のため、種々の負荷分散方式が提案されてきた。負荷分散方式は、静的負荷分散方式と動的負荷分散方式に分類することができる。さらに、動的負荷分散は、負荷情報の管理とタスク転送の決定を一台の計算機で行う集中制御型と、各計算機で独立して行う分散制御型に分けられる。本研究では[3]を基に、マルチキャストによるタスク転送要求の送出先の決定に対して遺伝的アルゴリズムを適用することで、より効率的な負荷情報の収集と利用を図る分散制御型動的負荷分散方式を提案する。また、UNIXネットワークで構成される分散システム上に実装し、模擬タスクを用いたシミュレーション実験により性能評価を行う。
• A proof of convergence on genetic algorithms with elitist schemes using inhomogeneous Markov chains

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  全国大会講演論文集  50-  (0)  285  -286  1995/03/15  [Not refereed][Not invited]
   

  本稿ではエリート戦略を有する遺伝的アルゴリズム(Genetic Algorithms,GA)に関して、非斉次マルコフ連鎖を用いた解析を行う。GAの収束性に関しては、マルコフ連鎖を用いた解析が従来行われてきたが、本論文では、非斉次マルコフ連鎖の遷移行列を用い、より簡明な収束性の証明を行う。さらにその結果を用いて、大域的最適解を得る確率に関する収束速度の下限を求めた。
• An application of a stochastic genetic algorithm to strategy acquisition in games played by groups

  Tomikawa Yuki, Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  情報処理学会研究報告. 人工知能研究会報告  95-  (23)  85  -90  1995/03/06  [Not refereed][Not invited]
   

  In this paper we discuss strategy acquisition in games played by the groups of agents. In such games, we have a huge number of possible of possible strategies because each agent in a group could take a different strategy. We employ StGA(a Stochastic Genetic Algorithm) which evaluates fitness values by using a stochastic learning automaton in order to realize effective learning in stochastic environments. The StGA samples a small number of strategies from all possible ones and applies stochastic learning and genetic operations to the sampled strategies. Through simulation experiments, we show the effectiveness of the StGAin the strategy acquisition.
• An Application of a Stochastic Genetic Algorithm to Strategy Acquisition in Games

  Tomikawa Yuki, Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  Bulletin of the Faculty of Engineering,Hokkaido University  (172)  p15  -22  1995/02
• A genetic load balancing scheme based on an internal model of nodes in distributed systems

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  IPSJ SIG Notes  94-  (105)  31  -36  1994/12/02  [Not refereed][Not invited]
   

  In this paper, we present a dynamic load balancing algorithm which learns a sending set of task migration requests. The algorithm is based on an internal model of nodes cousisting of FIFO and Round-Robin queues. In dynamic load balancing in general, we equalize each processor's load by migrating tasks from heavily-loaded processors to lightly-loaded ones. If we send task migration requests randomly or by a broadcast, many unnecessary messages will be sent. The proposed algorithm employs multicast messages which are sent to specified nodes. The sending set of the messages is coded into a genetic string to which genetic operations are applied.
• A Genetic Algorithm which has a Fitness Evaluation Mechanism by Stochastic Learning(1) : BasicModel

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  全国大会講演論文集  49-  (0)  231  -232  1994/09/20  [Not refereed][Not invited]
   

  従来の遺伝的アルゴリズム(Genetic Algorithms,以下GAと略す)では、正確な適合度値が必要なときに必要な数だけ求められることを暗黙の前提としている。しかし、実際の問題へ応用する場合、適合度評価に時間を要し、一度に多くの適合度値を計算することが現実的でないことがある。また、確率的な環境への適応学習などの場合、環境から得られる情報は、ある行動の成功・失敗の2値で示されるため、適合度の値として直接採用することはできない。本論文では、逐次的に適合度評価を行なうことで、確率的な環境に適応する遺伝的アルゴリズムStGA(Stochastic Genetic Algorithm)を提案する。StGAでは適合度の評価に確率学習オートマトン(Stochastic Learning Automata,SLA)を採用した。これにより、環境から得られる情報が成功・失敗の2値に限られ、かつ逐次的にしか評価値が得られない場合でも、適切な適合度値の分布を集団内に作り出す。また、StGAをSLAの改良とみなすこともできる。SLAには、状態空間のサイズが非常に大きな場合に、収束が著しく遅くなるという欠点がある。この欠点を改善するために、従来、連想記憶を用いた状態空間の圧縮などの対策が講じられてきたが、問題に依存した静的な方法であることから一般に広く用いることはできない。StGAでは、状態空間をGAの個体の形にコーディングし、集団という形で状態空間からサンプリングを行なって、それに対して遺伝的操作を適用することにより、問題に適応する形で状態空間の圧縮を実現することができる。本論文では、SLAのみの場合とシミュレーション実験により比較検討することを通して、GAによる状態空間の圧縮が収束性の向上に大きな効果があることを示す。
• A Genetic Algorithm which has a Fitness Evaluation Mechanism by Stochastic Learning(2) : AnApplicatingtoStrategyAcquisitionofGames

  Tomikawa Yuki, Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  全国大会講演論文集  49-  (0)  233  -234  1994/09/20  [Not refereed][Not invited]
   

  従来の遺伝的アルゴリズム(Genetic Algorithm,以下GAと略す)を、適合度値の評価に時間を要する問題や確率環境への適応学習に適用することは困難である。このような問題に対して、確率学習による適合度評価機構を有する遺伝的アルゴリズムStGA(stochastic Genetic Algorithm)が提案されている。StGAでは、適合度の評価に確率学習オートマトンSLA(stochastic Learning Automata)を用いている。SLAには、状態空間のサイズが非常に大きい場合に収束が著しく遅くなるという欠点がある。StGAはこの点を改善し、問題に適応する形で状態空間を圧縮することを目的としている。我々はStGAが状態空間の圧縮を行なうという点に着目し、これを戦略の種類が非常に多いゲームにおける戦略の獲得に応用できるのではないかと考えた。本論文では、StGAとSLAをゲームにおける戦略の獲得を行なう手段としてインプリメントして対戦を行ない、状態空間のサイズが大きい場合におけるStGAの有効性の検証を行なう。
• A Dynamic Loaad Balancing System using Genetic Algorithms and Stochastic Learning Automata

  Yamashita Takayuki, Munetomo Masaharu, Takai Yoshiaki, Sato Tishiharu  全国大会講演論文集  49-  (0)  251  -252  1994/09/20  [Not refereed][Not invited]
   

  複数の計算機をLANで接続して資源の共有を図る分散システムにおいて、計算機間で負荷の分散を行うことにより、応答時間の短縮や資源利用率の改善など、システム性能の向上を図ることができる。この目的のため、種々の負荷分散方式が提案されてきた。分散制御型の動的負荷分散方式に遺伝的操作を導入した手法として、遺伝的アルゴリズムと確率学習オートマトンによる動的負荷分散(GeSLA)に関する研究が行われている。この手法においては、タスク転送をどの計算機に対して要求するかを記述した文字列を遺伝的アルゴリズム(Genetic Algorithms,GA)における個体とし、その適合度値の更新に確率学習オートマトン(Stochastic Learning Automata,SLA)による確率的山登り法を適用している。本研究では、UNIXワークステーションをLANで接続した分散システム上にこの方式を実装し、実際に生成したタスクを用いた実験により性能評価を行う。
• An Efficient String Exchange Algorithm for a Subpopulation-Based Asynchronously Parallel Genetic Algorithm and Its Evaluation

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  IPSJ Journal  35-  (9)  1815  -1827  1994/09/15  [Not refereed][Not invited]
   

  We Present an efficient string exchange scheme on subpopulaiton-based parallel genetic algorithms. The subpopulation-based parallel genetic algorithm divides a population into subpopulations in which genetic operations are executed simultaneously. In this scheme, exchanging strings between subpopulations through communicating network is essential to avoiding performance degradation of genetic search due to uniformity of the subpopulation. To reduce unnecessary inter-processor communications is an important issue to realize efficient parallel computation. In conventional subpopulation-based ...
• A Dynamic Load Balancing Scheme Using Stochastic Learning Automata and Genetic Algorithms

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  情報処理学会研究報告. 人工知能研究会報告  94-  (20)  95  -102  1994/03/08  [Not refereed][Not invited]
   

  A distributed computing system is a collection of autonomous computers loosely connected via a communicating network whose latency is relatively large. In improving the system performance, it is important to keep the load of each processor even. On a distributed dynamic load balancing algorithm, each processor observes their load state and sends a task in order to balance their loads. In our scheme, we use a population of strings each of which stands for a set of processors to which requests of a task migration are sent, and genetic operations and stochastic learning are applied in order to realize efficient task migrations. Through empirical investigations using a simulator, we show the effectiveness of our scheme.
• A Genetic Scheme for Distributed Dynamic Load Balancing

  Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  Bulletin of the Faculty of Engineering,Hokkaido University  167-  (167)  p127  -135  1994/01  [Not refereed][Not invited]
  
• A Cooperative Search Strategy Using Hierarchical Genetic Algorithms and Its Implementation on the UNIX-Network

  Takahashi Masakazu, Munetomo Masaharu, Takai Yoshiaki, Sato Yoshiharu  情報処理学会研究報告. 人工知能研究会報告  93-  (103)  9  -16  1993/11/24  [Not refereed][Not invited]
   

  In a subpopulation-based parallel genetic algorithm (PGA), a population is divided into subpopulations to which genetic operations are applied simultaneously. We propose a hierarchical subpopulation-based PGA model that has an optimization mechanism of GA parameters for each subpopulation using a meta-level GA. In our model, parameters for genetic operations applied to a subpopulation are coded into a string referred to as a meta-code which is optimized via meta-level GA operations. Through exchanging information concerning meta-codes and subpopulations, the model realizes an effective search on a distributed computing environment. We implement the model on a local area network that consists of UNIX workstations.
• A Parallel Genetic Algorithm Based on the Adaptive Coding

  TAKAHASHI Masakazu, MUNETOMO Masaharu, TAKAI Yosiaki, SATO Yoshiharu  全国大会講演論文集  46-  (0)  301  -302  1993/03/01  [Not refereed][Not invited]
   

  遺伝的アルゴリズムは、生物の遺伝子の働きにヒントを得た最適化手法である。問題の対する多数の解候補を遺伝子の形にコーディングし、その適応度の高いものが増加してゆく「淘汰」(selection)2つの遺伝子内の部分情報を交換する「交叉」(crossover)、ある小さな確率で遺伝子内の情報が変化する「突然変異」(mutation)の基本3操作を一世代とし、それを繰り返すことによって近似最適解を得ようとするアルゴリズムである。しかし、一般的にコーディングやcrossover方法の設定に関しては、ビルディングブロック仮説を満たす必要がある。しかしながら。問題によってはこの仮説を常に満たすようなコーディング方法を求めることが困難な場合がある。その為、最適解に収束しない事も少なくない。そこで本稿では、コーディングを動的に変化させるadaptive codingを提案しナップザック問題を用いた数値実験によりその有効性を確認する。
• An Efficient Exchange Algorithm for Parallel GAs and Its Evaluation

  棟朝 雅晴, 高井 昌彰, 佐藤義治  情報処理学会研究報告アルゴリズム（AL）  1992-  (58)  41  -48  1992/07/17  

  遺伝子集団分割による並列遺伝的アルゴリズムにおける遺伝子交換アルゴリズムの改良とその評価を行なった結果について述べる。遺伝子集団の中に含まれるスキーマ数の減少を、その適合度の分布の標準偏差を計算することで間接的に評価し、遺伝子交換を行なう基準とすることで、遺伝子集団の中に含まれているスキーマの数の急速な減少を防ぎ、遺伝的アルゴリズムのスキーマ処理効率を維持する。そのために標準偏差と遺伝子集団内に含まれるスキーマの数について、Sigma?Hypothesisと呼ばれる仮説を立て、理論的解析とシミュレーション実験によりこれを検証した。さらに、この仮説に基づく遺伝子交換アルゴリズムについて、その有効性を実験により確認した。Improvement of exchange algorithms on parallel genetic algorithms and their evaluation are presented in this paper. To avoid rapid decrease of the number of schemata in a population and maintain efficient schema processing, the algorithm presented estimates indirectly the decrease of the number of schemata by using standard deviation of fitness distribution. We propose sigma-hypothesis and discuss its validity through some theoretical and empirical results. A parallel genetic algorithm based on the hypothesis is presented and some experiments are made to confirm its efficiency.

Industrial Property Rights

• 特開2002-305536:経路制御装置  2002/10/18

  棟朝 雅晴  北海道ティー・エル・オー株式会社  200903009432855247

Awards & Honors

• 2023/10 Information Processing Society of Japan IPSJ-CS Outstanding Achievement and Contribution Award
  
• 2017/09 情報処理学会数理モデル化と問題解決研究会 功績賞
   

  受賞者: 棟朝 雅晴
• 2009/03 The 10-th WSEAS international conference on Evolutionary Computation Best paper award
   

  受賞者: MUNETOMO Masaharu

Research Grants & Projects

• 集約的データ解析法による不正アクセス履歴の分析とサイバー攻撃予測への応用

  日本学術振興会：科学研究費助成事業

  Date (from‐to) : 2023/04 -2028/03 

  Author : 南 弘征, 棟朝 雅晴, 馬場 健一, 水田 正弘, 山岡 克式
• Heuristic algorithm of exploration and exploitation to the space geometry in ciliates and amoebae

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research

  Date (from‐to) : 2021/09 -2026/03 

  Author : 中垣 俊之, 棟朝 雅晴, 田中 良巳, 國田 樹, 佐藤 勝彦
• Advanced mechanics of cell behavior shapes formal algorithm of protozoan smartness awoken in giorama conditions.: Algorithms Evaluation Group

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (A)

  Date (from‐to) : 2021/09 -2026/03 

  Author : 中垣 俊之, 佐藤 勝彦, 田中 良巳, 棟朝 雅晴, 國田 樹
• Development and Implementation of Real World Scale Artificial Evolutionary Algorithms

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research

  Date (from‐to) : 2020/04 -2023/03 

  Author : 棟朝 雅晴

   

  令和３年度においては、大規模かつ困難な最適化問題の解決に必要となるアルゴリズムの開発を進め、スケーラブルなリンケージ同定手法の開発ならびに実問題への適用について研究を行った。具体的には、スケーラブルなリンケージ同定手法として、sLIEM (scalable Linkage Identification with Epistasis Measures)の開発ならびに、合成人口モデルに関わる最適化問題への適用を行った。進化計算において互いに関連のある遺伝子を同定するリンケージ同定手法は、個体長の2乗オーダーの計算量を必要とし、多項式オーダーではあるが大規模問題となった場合にその計算量が課題となる。本研究課題で開発したsLIEMは、重要な変数（遺伝子）に関する摂動を中心としてリンケージ同定の対象を絞り込むことで、その計算量を削減しつつ、実問題におけるリンケージ同定の精度を確保している。 スケーラブルなリンケージ同定手法の提供例として、村田らによる合成人口モデルに関わる最適化問題へ適用し、従来手法と比較した優位性を検証した。合成人口モデルは、公開されている自治体の人口分布に関する統計データから、住民それぞれの世帯構成を推定し合成することで、プライバシーを保護しつつ、社会シミュレーションに必要とされる基礎的な人口モデルを求める手法であり、従来手法においては擬似焼き鈍し法を用いた最適化手法が提案されていた。本研究で開発したスケーラブルなリンケージ同定を導入した並列進化計算を用いることで、生成される合成人口モデルの精度を向上（誤差を低減）することができた。また、スケーラブルなリンケージ同定に加え、さらにACO (Ant Colony Optimization)の大規模並列実装、実問題への応用についても検討に着手し、次年度にその成果を公表する計画である。
• 最適資源選択技術に関する研究（インタークラウドを活用したアプリケーション中心型オーバーレイクラウド技術に関する研究：主たる共同研究者）

  JST：CREST

  Date (from‐to) : 2015/10 -2021/03 

  Author : MUNETOMO Masaharu
• Development of a communication scheme for many site coupled calculations

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)

  Date (from‐to) : 2014/04 -2017/03 

  Author : KOBAYASHI Taizo, MUNETOMO Masaharu, JITSUMOTO Hideyuki, TAKAMI Toshiya, NANRI Takeshi, MORIE Yoshiyuki

   

  A big bottleneck in coupled simulations and large scale high performance computing is files I/O. In order to reduct this bottleneck, we have studied and developed a communication scheme of which processes are able to connect each other directly. (1) We have implemented a simple and compact communication library: NSTDIO. The interface of this communication library is designed based on "stdio" of C programing language. This library is enabled to download from GitHub https://github.com/y-morie/nstdio (2) We have developed and implemented a framework of jobs/processes cooperation on inter-site: EGCPOPS. This framework realizes jobs cooperation on inter-site without any administrator authority. This framework is also available from GitHub https://github.com/RyzeVia/exgcoup (3) Because of these framework work well, we have also studied and developed a conceptual design of mechanism for uncertainty: Self-Referential eXecutable: SRX.
• Study on High-Performance and Reliable Load Balancing Technology for Academic Federated Cloud Platforms

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)

  Date (from‐to) : 2012/05 -2016/03 

  Author : AIDA Kento, SAKANE Eisaku, MUNETOMO Masaharu, KOBAYASHI Taizo, Abdul-Rahman Omar

   

  Federated cloud organized by cloud platforms distributed over multiple sites is a promising platform for research and education in academic communities. However, a load balancing technology to assign application programs to suitable cloud platforms has not been established. In this project, we conducted the study on the load balancing technology that enabled high-performance and reliable computing by utilizing cloud platforms distributed over multiple sites. We proposed application performance models on cloud platforms and developed a software system to select suitable cloud platforms by collecting application performance characteristics.
• Extremely large-scale optimization problem-solving using robust and scalable evolutionary computation

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)

  Date (from‐to) : 2010/04 -2014/03 

  Author : MUNETOMO Masaharu

   

  We have developed a series of evolutionary algorithms such as BOA-MD, an extension of BOA introducing mixture distributions, BHCS by combining BOA with local search, ARGA and BRGA for MINLP (Mixed-Interger Non-Linear Programming). We also developed large-scale parallel evolutionary algorithms in a many core architecture and cloud computing environment. As applications to real-world problems, we applied evolutionary algorithms to optimal resource allocation problem in cloud computing environment as a MINLP problem, de novo ligand docking problems to find promising structures of medicines automatically, and so on, to show the effectiveness of our approach.
• アカデミックインタークラウドの実現に向けた連携基盤技術に関する研究

  国立情報学研究所：国立情報学研究所一般公募型共同研究

  Date (from‐to) : 2014 -2014 

  Author : 棟朝 雅晴
• Design and Development of Advanced IT Research Platform for Information Explosion Era

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Priority Areas

  Date (from‐to) : 2006 -2010 

  Author : ADACHI Jun, TANAKA Katsumi, NISHIDA Toyoaki, KUNIYOSHI Yasuo, SUDOH Osamu, KUROHASHI Sadao, HARA Takahiro, MATSUOKA Satoshi, TAURA Kenjiro, TATEBE Osami, MUNETOMO Masaharu, HIROTSU Toshio, MATSUBARA Jin, SHIMOJYO Shinji, CHIBA Shigeru, YUASA Taichi, MATSUYAMA Takashi, CHIKAYAMA Takashi, KONDO Toru, KONO Kenji, OKAMOTO Masahiro, AIDA Kento, KAMADA Tomio, KITSUREGAWA Mararu, YAMANA Hayato, NAKAMURA Yutaka, KOBAYASHI Hiroaki, NAKAJIMA Hiroshi

   

  This project implemented a common research infrastructure for all the research groups participating in this priority-area research initiative, accordingly supported all research activities in this initiative. Providing this infrastructure, we succeeded in accelerating shared utilization of research facilities and resources within the limitation of research funding and strengthening the collaboration among research groups. These shared facilities include (a)TSUBAKI: a open search engine for large-scale corpus, (b)InTrigger : Widely-distributed computing test-bed, (c)IMADE : an environment for real-world interaction measurement and analysis, and (d) prototyping for sensor-network based preventive medicine.
• Design Optimization using Large-Scaled Parallel Evolutionary Algorithms with Gene Analysis

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B)

  Date (from‐to) : 2006 -2008 

  Author : MUNETOMO Masaharu

   

  本研究においては、遺伝子解析による高度な進化計算アルゴリズムを大規模並列化するとともに、グリッドコンピューティングシステムなど最新の大規模並列計算環境における実装を行った。さらには、最適化問題を解きたい設計者の有するシミュレーションプログラムとの連携を容易に行うためのフレームワークを提案することで、大規模かつ複雑な現実の設計問題、最適化問題を解決するための基盤となるシステムのプロトタイプを開発した。
• メタ計算の進化的探索に基づく正当で効率的なプログラムの自動生成

  日本学術振興会：科学研究費助成事業 萌芽研究

  Date (from‐to) : 2004 -2005 

  Author : 赤間 清, 棟朝 雅晴

   

  メタ計算は、仕様から正当なプログラムを生成するための新しい方法である。 メタ計算では、計算状態の束をメタ節集合で表現し、メタルールで変換を次々に行うことによって新しいメタ節を得る。最初と最後のメタ節集合のペアから正当なルールを得ることができ、そのようなルールを集めることによって、プログラムを得ることができる。 得られたプログラムの(部分)正当性は、個々のメタルールの正当性から保証できる。 正しいメタルールを仕様から作る方法もすでに与えられている。 このルール生成のパラメータは、最初のメタ節集合とルール適用の2つである。ルール適用は、メタ節集合のどの位置にどのメタルールを適用するか、それを何回繰り返すかである。本研究では、これらのパラメータを遺伝子にコーディングして、進化的探索によって、よりよいルールを低コストで発見する方法を提案した。その際、ルールの評価として、分岐数が少なく、節のサイズが小さいものを優先する指標を用いた。 ポイントとなるのは遺伝子へのコーディングである。ルール適用の可能性はそのときのメタ節集合によって大きく変わるので、あらかじめ遺伝子の空間を固定するのは得策ではない。そこで、メタ節集合とメタルールが与えられたとき、ルール適用の可能性の集合を高速に計算する手法や、その中のルール適用の1つの可能性をメタ節集合に適用して、次のメタ節集合を求める手法を考案し、それらをET言語に組み込み述語として導入した。これにより、メタ計算を基礎とした進化的探索のアルゴリズムの実現が容易になり、メタ計算の探索に基づくプログラム生成を効率的に行うことが可能になった。
• 遺伝子解析に基づく遺伝的アルゴリズムの開発とシステム設計への応用

  日本学術振興会：科学研究費助成事業 若手研究(B)

  Date (from‐to) : 2003 -2005 

  Author : 棟朝 雅晴

   

  本研究においては、これまでに提案されたリンケージ同定に基づく遺伝的アルゴリズムをさらに発展させ、より一般的な枠組みとして、遺伝子解析に基づく遺伝的アルゴリズムを開発することを目的とし、さらにそのシステム設計問題への応用をはかっている。バイオインフォマティクスの分野では、遺伝子解析に関する手法が数多く提案されているが、それらを参考にリンケージの同定、ビルディングブロックの検出、交叉手法の改良などを行い、より高性能で高い信頼性を有する遺伝的アルゴリズムを開発する。 本年度においては、分布推定手法の改良を図るとともに、効率的な並列化手法を開発することで、大規模な問題への対応を図った。具体的には、割り当て関数による重み付けを行うことで精度を向上させ分布推定に要する計算コストを削減するための手法を開発するとともに、ベイジアンネットワークに基づく確率モデル構築を行う分布推定アルゴリズムにおいて、ネットワーク構築の効果的な並列化手法を開発した。 さらには、リンケージ同定と分布推定アルゴリズムの双方の利点を組み合わせたアルゴリズムD^5の開発を行い、問題規模の増大に対するスケーラビリティに優れた手法を開発した。さらに、D^5の実数値問題への適用についても議論するとともに、その性能について評価を行った。 提案手法の適用例として、特に、蛋白質の構造エネルギー最小化問題へ、並列化した分布推定による探索手法を適用することで、本研究で開発した手法の有効性を検証している。
• 遺伝的アルゴリズムの設計理論の確立およびその大規模分散システム設計への応用

  日本学術振興会：科学研究費助成事業 若手研究(B)

  Date (from‐to) : 2001 -2002 

  Author : 棟朝 雅晴

   

  本研究においては、線型・非線型および単調・非単調性を調べることによって関連する遺伝子座のまとまりであるリンケージ集合を同定し、効果的な交叉を実現する手法に関してその理論的基礎を確立するとともに、理論に基づいた遺伝的アルゴリズムの設計、特に交叉手法の改良を行うことで、大規模な最適化問題におけるアルゴリズムの性能を評価した。リンケージ集合の構造として、これまでの研究では比較的単純な線形の構造が仮定されていたが、本研究では階層構造を有するリンケージの同定を行う手法である、hLIEM(hierarchical Linkage Identification with Epistasis Measure)およびhLIEM^2(hierarchical Linkage Identification with Epistasis Measure considering Monotonicity)を開発した。これら手法においては、小さなリンケージ集合をまとめてより大きなリンケージ集合を生成するという過程を繰り返すことで、現実問題の多くが有すると考えられる問題の階層構造を同定することが可能となり、交叉など遺伝的操作をさらに効率的に適用することが可能となった。 本研究で開発した階層型のリンケージ同定アルゴリズムの有効性を、階層型のトラップ関数に代表される各種のテスト関数において確認したが、さらに現実の問題として都市圏ネットワーク設計問題へと適用し、その有効性を確かめた。大規模なネットワークを設計する場合、ゆるやかな階層構造を有するようなネットワークとして設計を行うことが考えられるが、本研究で提案するアルゴリズムにより、人間の設計者が介在することなく、計算機により自動的に適切な階層構造を有するネットワークを構成することができ、従来の手法に比べて、より低コストで高性能なネットワークを設計することができた。
• Construction of Program Synthesis System Based on Equivalent Transformation

  Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)

  Date (from‐to) : 2000 -2002 

  Author : AKAWA Kiyoshi, MUNETOMO Masaharu, MIZUTA Masahiro

   

  1. Development of a general theory of meta-computation We developed a general theory for program synthesis based on a new class of representation called separated descriptions. We clarified the fundamental difference between program transformation and fule generation, and showed that program transformation can be regarded as a part of our program synthesis. 2. Extension of the program sysnthesis system using first-order expressions We constructed an expertimental program synthesis system, which automatically synthesizes a program by repeatedly generating and accumulating new rules. We obtained several successful results. For example, the system can automatically synthesize, from a definition of a language represented by a first-order expression, a program corresponding to a finite automaton that recognizes the language. 3. Extension of meta-computation We extended meta-decriptions to improve the system to be able to generate a larger class of rules. We introduced expressions of constraints on variables and extended a theory of meta-computation. This enabled the system to generate with applicability conditions and can be more controllable. We also investigated a theoretical foudation of generation of such rules. 4. Evaluation of the program synthesis system We applied the system to generation of parser programs. Highly optimized programs are obtained at the experiments. However they can be more efficient by optimization of execution parts of rules and by transforming the rules into deterministic ones. Although we conducted them manually, complete automation is a future work.
• 通信資源管理への人工進化モデルの適用とその大規模ネットワークにおける評価

  日本学術振興会：科学研究費助成事業 奨励研究(A)

  Date (from‐to) : 1999 -2000 

  Author : 棟朝 雅晴

   

  本研究では、進化的計算手法、特に遺伝的アルゴリズムを用いた経路制御アルゴリズムに関して、大規模ネットワーク上での性能評価を行い、アルゴリズムの改良を行った。改良点としては、適応度を評価するために必要なネットワーク状態の観測法について、従来は評価パケットが到着するまでの時間を用いていたのに対し、改良したアルゴリズムでは各リンクの負荷状態を離散化した情報を収集することでより高速かつ効率的にネットワークの負荷状態を観測することができた。さらには代替経路を生成するために使用される遺伝的操作に関してもリンクの負荷状態を考慮した交叉および突然変異の手法を開発することでアルゴリズムの改良を行った。提案したアルゴリズムの評価を行うため、イベントシミュレーション手法に基づくネットワークシミュレータを開発し、大規模シミュレーションにより改良手法の有効性を確認した。 本研究では、さらに、ネットワーク資源管理アルゴリズムとして分散型帯域幅割当アルゴリズムを開発した。特定の通信リンクや小規模ネットワークを対象とした場合、通信帯域割当などの資源管理は集中管理方式により比較的容易に行うことができるが、大規模ネットワーク上においては、必然的に不確実な情報を基にした分散管理を行わざるを得なくなり、単純な最適化問題としてとらえることはできない。このような状況において、遺伝的アルゴリズムを用いた分散型帯域幅割当アルゴリズムを構築し、その有効性をシミュレータによるシミュレーション実験と通して検証した。
• 進化的計算手法を用いた適応型経路制御アルゴリズムの構築

  日本学術振興会：科学研究費助成事業 奨励研究(A)

  Date (from‐to) : 1997 -1998 

  Author : 棟朝 雅晴

   

  本研究では、複雑系、人工生命に関連して近年注目を集めている遺伝的アルゴリズムをインターネットにおける経路制御アルゴリズムへ応用することで、ネットワークの負荷変化に動的するアルゴリズムを構築する。 現在一般に使用されているルーティングアルゴリズムでは、ネットワークの負荷状態や通信リンクの性能などを考慮せず、単純に通過したゲートウェイの数で表されるホップカウント距離を用いていた。そこで、ネットワークの負荷状態を考慮した適応型のルーティングアルゴリズムを少ない通信負荷で実現するため、遺伝的アルゴリズムにより必要な代替経路群を動的に生成するアルゴリズムを構築した。 代替経路を効率的に生成するため、特別に設計された経路遺伝的操作(Path Genetic Operators)を提案した。提案するルーティングアルゴリズムにおいては、初期経路として、従来と同様のホップカウント距離に基づいた最短経路を使用し、ある一定回数以上使用される経路に関して、代替経路を動的に生成し、各代替経路の通信遅延に応じてパケットを分配する。通信遅延の観測に関しては、ルーティングテーブルに存在する各経路に関して、定期的に通信遅延の観測パケットを送出するが、ルーティングテーブルには頻繁に使用される少数の代替経路のみ存在するため、少ない通信負荷で効果的な観測が行われる。 アルゴリズムの評価を行うため、離散事象シミュレータを構築し、その上でシミュレーション実験を行い、従来の代表的な手法であるRIP,SPFと比較した。その結果、今回提案した基本的なアルゴリズムにより、ネットワークの負荷が減少し、効果的に通信パケットが送出されていることが確かめられた。

Educational Activities

Teaching Experience

Position History

• 2019年4月1日 

  - 

  2021年3月31日 

  教育研究評議会評議員
• 2021年4月1日 

  - 

  2023年3月31日 

  教育研究評議会評議員
• 2023年4月1日 

  - 

  2024年3月31日 

  研究戦略室室員
• 2013年4月1日 

  - 

  2015年3月31日 

  情報基盤センター副センター長
• 2015年4月1日 

  - 

  2017年3月31日 

  情報基盤センター副センター長
• 2017年4月1日 

  - 

  2019年3月31日 

  情報基盤センター副センター長
• 2019年4月1日 

  - 

  2021年3月31日 

  情報基盤センター長
• 2021年4月1日 

  - 

  2023年3月31日 

  情報基盤センター長
• 2023年4月1日 

  - 

  2025年3月31日 

  情報基盤センター長

Committee Membership

• 2022/10 - Today   The Japanese Society of Evolutionary Computation   President
• 2020/10 -2022/09   The Japanese Society of Evolutionary Computation   Vice President