We propose a new technique for generating a small set of patterns to estimate the maximum power supply noise of deep sub-micron designs. We first build the charge/discharge current and output voltage waveform libraries for each cell, taking power and ground pin characteristics, the power net RC and other input characteristics as parameters. Based on the cells current and voltage libraries, the power supply noise of a 2-vector sequence can be estimated efficiently by a cell-level waveform simulator. We then apply the genetic algorithm based on the efficient waveform simulator to generate a small set of patterns producing high power supply noise. Finally, the results are validated by simulating the obtained patterns using a transistor level simulator. Our experimental results show that the patterns generated by our approach produce a tight lower bound on the maximum power supply noise.