Tianshi Chen (陈天石)

Research Experiences

Research Assistant (09/2005 - 07/2010), School of Computer Science and Technology, University of Science and Technology of China, Hefei, China.

Research Issue: Theoretical Foundations of Population-based Evolutionary Algorithms
Understanding Evolutionary Algorithms (EAs) is essential to aid the design of practical EAs in real-world applications. However, researchers even did not know the time complexities of population-based EAs on the simplest optimization problem instances, the unimodal instances. Concerning the above issue, we proposed a general approach for analyzing time complexity of various population-based EAs on unimodal instances of combinatorial optimization problems. Being built upon the Markov model and super-martingale model, this approach characterizes the optimization process of each population-based EA on unimodal instances as repeated takeover-upgrade processes. Consequently, researchers can easily obtain the upper bound of average time complexity of EAs on different unimodal problem instances. In addition, this approach can also be generalized to analyze EAs on some multimodal problem instances. The related papers were published by IEEE Transactions on Systems, Man, and Cybernetics: Part B, Cybernetics and Theoretical Computer Science.

Visiting Research Student (03/2009 - 01/2010), Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China.

Research Issue: Verification of Godson Microprocessor with Computational Intelligence Techniques
Simulation-based verification is a widely-used methodology for validating modern microprocessor. A crucial characteristic of simulation-based verification is that it requires a large number of test programs, especially when the Design Under Verification (DUV) is very complex. To avoid excessive human efforts spent in writing test programs manually, automatic test program generation has received extensive investigations over the past decade. In this project, we propose a novel approach for coverage-irected automatic test program generation, which is named XGen. XGen incorporates state-of-art computational intelligence techniques into the hierarchical algorithmic architecture, which is powerful for modeling and generating high-quality test programs.

Research Issue: Clocks and Orders in Multiprocessor Systems
Lamport's logical clock and logical time order are important concepts for distributed systems. However, in many applications one often needs to face the high computational costs caused by the lack of logical time order information in practice. The costs are mainly spent on conjecturing more order information from the observable but fragmentary logical time order information. To cope with the above problem, we proposed to rewake the idea of global clock for multiprocessor systems, and the purpose is to obtain more order information. A new concept called pending period, which is a relaxed time interval in which an instruction starts and ends, is proposed on the basis of global clock. As a consequence, the physical time order can be defined as an order between two instructions with disjoint pending periods. By pending period and the resultant physical time order, many logical time orders in the execution of a parallel program can be easily inferred, which significantly reduces the time complexity of solving many important application problems in multiprocessor systems. The related papers were accepted/published by premier computer architecture conferences International Symposium on Computer Architecture (ISCA) and International Symposium on High-Performance Computer Architecture (HPCA).

Visiting Research Associate (11/2009 - 12/2009), School of Computer Science, University of Birmingham, Birmingham, UK.

Research Issue: Time Complexity Analysis of Estimation of Distribution Algorithms
Estimation of distribution algorithms (EDAs) are widely used in stochastic optimization. Impressive experimental results have been reported in the literature. However, little work has been done on analyzing the computation time of EDAs in relation to the problem size. It is still unclear how well EDAs (with a finite population size larger than two) will scale up when the dimension of the optimization problem (problem size) goes up. We studied the computational time complexity of a simple EDA, i.e., the univariate marginal distribution algorithm (UMDA), in order to gain more insight into EDAs complexity. First, we discuss how to measure the computational time complexity of EDAs. A classification of problem hardness based on our discussions is then given. Second, we prove a theorem related to problem hardness and the probability conditions of EDAs. Third, we propose a novel approach to analyzing the computational time complexity of UMDA using discrete dynamic systems and Chernoff bounds. Following this approach, we are able to derive a number of results on the first hitting time of UMDA on a well-known unimodal pseudo-boolean function, i.e., the LeadingOnes problem, and another problem derived from LeadingOnes, named BVLeadingOnes. Although both problems are unimodal, our analysis shows that LeadingOnes is easy for the UMDA, while BVLeadingOnes is hard for the UMDA. Finally, in order to address the key issue of what problem characteristics make a problem hard for UMDA, we discuss in depth the idea of "margins" (or relaxation). We prove theoretically that the UMDA with margins can solve the BVLeadingOnes problem efficiently. The related paper was published by IEEE Transactions on Evolutionary Computation.

Publications

Refereed Journal Papers & Selected Technical Reports

1. Weiwu Hu, Yunji Chen, Tianshi Chen, Cheng Qian, and Lei Li, "Linear Time Memory Consistency Verification", accepted by IEEE Transactions on Computers, 2011. 
2. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao, "A Large Population Size Can be Unhelpful in Evolutionary Algorithms," accepted by Theoretical Computer Science, 2011. EC, Th
3. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao, "Analysis of Computational Time of Simple Estimation of Distribution Algorithms," IEEE Transactions on Evolutionary Computation, vol. 14, no. 1, pp. 1-22, 2010. [PDF] (The 1st most accessed paper in IEEE Transactions on Evolutionary Computation in March 2010) EC, Th
4. Tianshi Chen, Jun He, Guangzhong Sun, Guoliang Chen, and Xin Yao, "A New Approach to Analyzing Average Time Complexity of Population-based Evolutionary Algorithms on Unimodal Problems," IEEE Transactions on Systems, Man, and Cybernetics: Part B, vol. 39, no. 5, pp. 1092-1106, 2009. [PDF] EC, Th
5. Tianshi Chen, Jun He, Guoliang Chen, and Xin Yao, "Choosing Selection Pressure for Wide-gap Problems," Theoretical Computer Science, vol. 411, no. 6, pp. 926-934, 2010. [PDF] EC, Th
6. Xin Yu, Ke Tang, Tianshi Chen, and Xin Yao, "Empirical Analysis of Evolutionary Algorithms with Immigrants Schemes for Dynamic Optimization," Memetic Computing, vol. 1, no. 1, pp. 3-24, 2008. [PDF] EC
7. Pengyu Wang, Yunji Chen, Haihua Shen, Tianshi Chen, and Heng Zhang, "Memory Consistency Verfication of Chip Multiprocessor," Journal of Software, in press (In Chinese). PC
8. Tianshi Chen, Ke Tang, Xin Yu, Guoliang Chen, and Xin Yao, "Adaptation of Mutation Rate is not a Panacea," NICAL-TR09, June, 2009. EC, Th
9. Yunji Chen, Tianshi Chen, and Weiwu Hu, "Global Clock, Physical Time Order and Pending Period Analysis in Multiprocessor Systems," CoRR abs/0903.4961, March 2009. PC, Th
   



Refereed Conference Papers

10. Qi Guo, Tianshi Chen, Haihua Shen, Yunji Chen, Yue Wu and Weiwu Hu, "Empirical Design Bugs Prediction for Verification," accepted by 2011 Design, Automation and Test in Europe Conference (DATE'11), Grenoble, France.
11. Qi Guo, Tianshi Chen, Haihua Shen, Yunji Chen, and Weiwu Hu, "On-the-fly Reduction of Stimuli for Functional Verification," In Proceedings of 19th IEEE Asian Test Symposium (ATS'10), Shanghai, China, 2010.
12. Yunji Chen, Weiwu Hu, Tianshi Chen, and Ruiyang Wu, "LReplay: A Pending Period Based Deterministic Replay Scheme," In Proceedings of 37th ACM IEEE International Symposium on Computer Architecture (ISCA'10),  Saint-Malo, France, 2010. (Acceptance Ratio 17.9%: 44 out of 245) PC
13. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao, "Rigorous Time Complexity Analysis of Univariate Marginal Distribution Algorithm with Margins," In Proceedings of 2009 IEEE Congress on Evolutionary Computation (CEC'09), Trondheim, Norway, 2009. EC, Th
14. Tianshi Chen, Per Kristian Lehre, Ke Tang, and Xin Yao, "When Is an Estimation of Distribution Algorithm Better than an Evolutionary Algorithm," In Proceedings of 2009 IEEE Congress on Evolutionary Computation (CEC'09), Trondheim, Norway, 2009. EC, Th
15. Zai Wang, Tianshi Chen, Ke Tang, and Xin Yao, "A Multi-objective Approach to Redundancy Allocation Problem in Parallel-series Systems," In Proceedings of 2009 IEEE Congress on Evolutionary Computation (CEC'09), Trondheim, Norway, 2009. EC
16. Yunji Chen, Ke Tang, and Tianshi Chen, "A Stochastic Method for Controlling the Scaling Parameters of Cauchy Mutation in Fast Evolutionary Programming," In Proceedings of 2009 IEEE Congress on Evolutionary Computation (CEC'09), Trondheim, Norway, 2009. EC
17. Yunji Chen, Yi Lv, Weiwu Hu, Tianshi Chen, Haihua Shen, Pengyu Wang, and Hong Pan, "Fast Complete Memory Consistency Verification," In Proceedings of 15th International Symposium on High-Performance Computer Architecture (HPCA-15). (Acceptance Ratio 19%: 35 out of 184; The first HPCA paper from Mainland China) PC, Th
18. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao, "On the Analysis of Average Time Complexity of Estimation of Distribution Algorithms," In Proceedings of 2007 IEEE Congress on Evolutionary Computation (CEC'07), Singapore, 2007, pp. 453-460. EC, Th
19. Tianshi Chen, Ke Tang, and Xin Yao, "Theoretical Investigations of Evolutionary Algorithms at NICAL," In Proceedings of Inaugural Symposium on Parallel Algorithms, Architectures and Programming (PAAP'08) , Hefei, China. EC, Th
    

Professional Activities

Membership


• IEEE student member (since 2007)

 

• IEEE 2011 Symposium on Foundations of Computational Intelligence (FOCI'11)

 
        Journal & Conference Review

• IEEE Transactions on Evolutionary Computation (IEEE Press)
• Theoretical Computer Science (Elsevier)
• Memetic Computing (Springer)
• Frontiers of Computer Science in China (Springer)
• IEEE 2008 World Congress on Computational Intelligence (WCCI'08)
• IEEE 2009 Congress on Evolutionary Computation (CEC'09)
• IEEE 2010  World Congress on Computational Intelligence (WCCI'10)
• 11th International Conference on Parallel Problem Solving From Nature (PPSN'10)


Talks


• On the Analysis of Average Time Complexity of Estimation of Distribution Algorithms (CEC'07, Singapore)
• Theoretical Investigations of Evolutionary Algorithms at NICAL (IWNICA'08, Hefei)
• Physical Time Order in Multiprocessor Systems (ICT, Beijing)
• Theoretical Investigations of Evolutionary Algorithms (Microsoft Research Asia, Beijing)