Web services run in a highly dynamic environment, as a result of which the QoS will change relatively frequently. In order to make the composite service adapt to such dynamic property of web services, we propose an adaptive approach for web service composition. This approach uses an EX-QoS model which makes the approach applicable in the decentralized service composition to achieve global optimization. Besides this, in order to make the composite service adjust itself quickly when execution problems occur, this paper uses replacement composite services backed up before the execution. Then, when a service fails, the composite service can easily switch to the replacement without affecting the runtime performance. In order to preserve the availability of the replacement, a re-selection for updating the replacement is used which is on the basis of a performance prediction to make the re-selection complete as early before the invocation of the failed service as possible. Experiments show that the proposed solutions have better performance in supporting the adaptive decentralized service composition.