ICCS 2018 Main Track (MT) Session 1
Time and Date: 13:35 - 15:15 on 11th June 2018
Chair: Travis Desell
| Optimizing the Efficiency, Vulnerability and Robustness of Road-based Para-transit Networks using Genetic Algorithm [abstract]
Abstract: In the developing world, majority of people usually take para-transit services for their everyday commutes. However, their informal and demand-driven operation, like making arbitrary stops to pick up and drop off passengers, has been inefficient and poses challenges to efforts in integrating such services to more organized train and bus networks. In this study, we devised a methodology to design and optimize a road-based para-transit network using a genetic algorithm to optimize efficiency, robustness, and invulnerability. We first generated stops following certain geospatial distributions and connected them to build networks of routes. From them, we selected an initial population to be optimized and applied the genetic algorithm. Overall, our modified genetic algorithm with 20 evolutions optimized the 20% worst performing networks by 84% on average. For one network, we were able to significantly increase its fitness score by 223%. The highest fitness score the algorithm was able to produce through optimization was 0.532 from a score of 0.303.
|Briane Paul Samson, Gio Anton Velez, Joseph Ryan Nobleza, David Sanchez and Jan Tristan Milan
| Learning network properties through optimizing principal eigenvector localization [abstract]
Abstract: Networks furnish a mathematical framework to model and decipher the collective behavior of the complex real-world systems. Scrutiny of principal eigenvector (PEV) and the corresponding eigenvalue of the networks are known to provide an understanding of various local and global structural as well as the dynamical evolution of the networks. Recently scrutiny of eigenvector localization has received tremendous attention in network science due to its versatile applicability in many different areas which includes analyzing centrality measure, spectral partitioning, development of approximation algorithms and disease spreading phenomenon. Moreover, lower order eigenvectors have been studied to develop machine learning tools. They used inverse participation ratio (IPR) as well as another kind of measure for the eigenvector localization, called as statistical leverage score which has an impact on modern big data analysis. One key factor of our interest is to understand properties of networks which may help in spreading or restricting perturbation in networks captured by the PEV localization. For a network, an eigenvector is said to be localized when most of its components are near to zero, with few taking very high values. To study the structural and spectral properties of networks as PEV changes its state from the delocalized to a highly localized, we evolve an initial random network. We develop randomized algorithms considering the IPR as an objective function. We demonstrate that PEV localization is not a consequence of a single network property and rather requires collective impact of several structural features. The final optimized network possesses a special structure independent of the initial network. It reveals that optimized network consists of two graph components of different sizes which are connected to each other via a single node (in Fig. 1). Moreover, the optimized structure contains a special set of edges, rewiring any one of them leads to a complete delocalization of the PEV from a highly localized state (Fig. 2). This sensitivity of the PEV at the most localized state turns out to be related to the behavior of the largest and the second largest eigenvalue of the network. Precisely when the network becomes most localized, the second largest eigenvalue of the adjacency matrix become very close to the largest eigenvalue (Fig. 3). Furthermore, we identify an evolution regime where networks are as localized as the optimized one, but, are robust to single edge rewiring (in Fig. 2). Moreover, we use the Susceptible-Infected-Susceptible (SIS) disease spreading model and verify that the structure of the networks in the intermediate and optimized stages slows down the spreading process than the initial random structure (Fig. 4).
|Priodyuti Pradhan and Sarika Jalan
| On the Configuration of Robust Static Parallel Portfolios for Efficient Plan Generation [abstract]
Abstract: Automated Planning has achieved a significant step forward in the last decade, and many advanced planning engines have been introduced. Nowadays, increases in computational power are mostly achieved through hardware parallelisation. In view of the increasing availability of multicore machines and of the intrinsic complexity of designing parallel algorithms, a natural exploitation of parallelism is to combine existing sequential planning engines into parallel portfolios. In this work, we introduce three techniques for an automatic configuration of static parallel portfolios of planning engines. The aim of generated portfolios is to provide a good tradeoff performance between coverage and runtime, on previously unseen problems. Our empirical results demonstrate that our techniques for configuring parallel portfolios combine strengths of planning engines, and fully exploit multicore machines.
|Mauro Vallati, Lukas Chrpa and Diane Kitchin
| A High-Performance Evolutionary Computation Framework for Scalable Spatial Optimization [abstract]
Abstract: Spatial optimization (SO) is an important and prolific field of interdisciplinary research. Spatial optimization methods seek optimal allocation or arrangement of spatial units under constraints such as distance, adjacency, and contiguity. Evolutionary Algorithms (EA) are well-known heuristic approach for solving SO problems. However, as spatial granularity becomes finer and problem formulations comprise increasingly complex spatial relationships, EA solvers must be adapted with greater computational efficiency and algorithmic effectiveness. We present a solution that addresses the efficiency issue by leveraging massive computing power on supercomputers. The computational scalability challenge is tackled with a parallel EA library that eliminates the costly global synchronization in massively parallel computing environment. Our implementation scales to 131,072 processors on the Blue Waters supercomputer. We develop novel spatially explicit EA recombination operators that implement crossover and mutation using intelligently guided strategies in spatially constrained decision space, inspired by path relinking and ejection chain heuristics. Our high-performance EA framework is employed as a computational solution for the complex problem of political redistricting in the United States. It enables the creation of billions of feasible districting plans that adhere to U.S. Supreme Court mandates and further facilitates statistical analysis of gerrymandering.
|Yan Liu and Wendy K. Tam Cho