A method of E-workflow composition based on distributed awareness is proposed. The mobile agent represents E-service and constitutes an autonomic unit. The E-workflow composition is achieved by the evolution of the mobile agent based on the semantic negotiation. By understanding properties of messages, the mobile agent use projection-join closure to capture such message situations, the optimization of the E-workflow composition is translated into dynamic services selection with QoS global optimization. We propose an improved algorithm based on quick sort and NSGA-II to resolve it. The simulation results show that the approach can significantly improve the E-workflow performance. It adapts well to the changes of dynamic environments.